03.1 单链表反转

2024 年 7 月 18 日 星期四(已编辑)
这篇文章上次修改于 2024 年 7 月 18 日 星期四,可能部分内容已经不适用,如有疑问可询问作者。

03.1 单链表反转

单链表反转:改变链的方向

单链表反转是一种常见而重要的链表操作,它可以改变链表的方向,使得原先的尾节点成为新的头节点。

1. 单链表反转的基本原理

单链表反转的核心思想是通过改变节点之间的链接方向,将链表的尾部连接到头部。这个操作可以通过遍历链表并逐个调整节点的 next 指针来实现。

2. Python单链表反转的实现方式

2.1 迭代法

迭代法是一种直观而简单的实现方式,通过遍历链表,逐个改变节点的 next 指针方向。以下是一个使用迭代法的示例(使用Python):

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def reverse_linked_list(head):
    prev = None
    current = head

    while current is not None:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node

    return prev

# 示例使用
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
reversed_head = reverse_linked_list(head)

# 输出反转后的链表
current = reversed_head
while current is not None:
    print(current.value, end=" -> ")
    current = current.next
print("None")

2.2 递归法

递归法是一种更为巧妙的实现方式,通过递归地反转子链表,并调整当前节点的指针。以下是一个使用递归法的示例(使用Python):

def reverse_linked_list_recursive(head):
    if head is None or head.next is None:
        return head

    new_head = reverse_linked_list_recursive(head.next)
    head.next.next = head
    head.next = None

    return new_head

# 示例使用
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
reversed_head_recursive = reverse_linked_list_recursive(head)

# 输出递归反转后的链表
current = reversed_head_recursive
while current is not None:
    print(current.value, end=" -> ")
    current = current.next
print("None")

3. Java单链表反转的实现方式

实现思路:

  1. 先定义一个节点 reverseHead = new HeroNode();
  2. 从头到尾遍历,每遍历一个节点就将其取出并放在新链表的最前端
  3. 原来的链表head.next = reverseHead.next
package org.example;  
  
import static org.example.SinglelinkedList.*;  
  
public class SingleLinkedListDemo {  
    public static void main(String[] args) {  
        HeroNode heroNode1 = new HeroNode(1, "一号", "1号");  
  
        HeroNode heroNode2 = new HeroNode(2, "二号", "2号");  
  
        HeroNode heroNode3 = new HeroNode(3, "三号", "3号");  
  
        HeroNode heroNode4 = new HeroNode(4, "四号", "4号");  
  
        HeroNode heroNode5 = new HeroNode(4, "五号", "5号");  
  
        HeroNode heroNode6 = new HeroNode(6, "六号", "6号");  
  
//        创建链表  
        SinglelinkedList singlelinkedList = new SinglelinkedList();  
//        加入  
        singlelinkedList.add(heroNode1);  
        singlelinkedList.add(heroNode2);  
        singlelinkedList.add(heroNode3);  
        singlelinkedList.add(heroNode4);  
  
        singlelinkedList.list();  
        singlelinkedList.del(heroNode3);  
        singlelinkedList.list();  
        System.out.println("有效的节点个数:" + getLength(singlelinkedList.getHead()));  
  
        singlelinkedList.addByOrder(heroNode5);  
        singlelinkedList.addByOrder(heroNode6);  
        singlelinkedList.addByOrder(heroNode3);  
        singlelinkedList.list();  
  
//        HeroNode res = findLastIndexNode(singlelinkedList.getHead(), 2);  
//        System.out.println(res);  
        System.out.println("反转单链表-------");  
        reverseList(singlelinkedList.getHead());  
        singlelinkedList.list();  
    }  
}  
  
//定义SingleLinkedList来管理角色  
class SinglelinkedList {  
  
    //返回头节点  
    public HeroNode getHead() {  
        return head;  
    }  
  
    //    初始化头节点,不动头节点  
    private HeroNode head = new HeroNode(0, "", "");  
  
    public void add(HeroNode heroNode) {  
        //    添加节点搭配单向链表  
        //    思路:不考虑编号顺序时,  
        //    找到当前链表的最后节点,并将其next指向新的节点  
        HeroNode temp = head;  
//        遍历链表,找到最后一个  
        while (true) {//退出循环时,temp指向最后  
            if (temp.next == null) {  
                break;  
            }  
            temp = temp.next;  
        }  
        temp.next = heroNode;  
    }  
  
    public void addByOrder(HeroNode heroNode) {  
        HeroNode temp = head;  
//        temp位于添加的前一个节点  
        boolean flag = false;//添加的编号是否存在  
        while (true) {  
            if (temp.next == null) {//处在链表最后  
                break;  
            }  
            if (temp.next.no > heroNode.no) {//位置找到了  
                break;  
            } else if (temp.next.no == heroNode.no) {  
                flag = true;//说明编号存在  
                break;  
            }  
            temp = temp.next;  
        }  
//        判断flag  
        if (flag) {  
            System.out.println("准备插入的编号已经存在,不能加入");  
        } else {  
            //添加到链表中  
            heroNode.next = temp.next;  
            temp.next = heroNode;  
        }  
    }  
  
    //    根据no修改节点的信息  
    public void update(HeroNode heroNode) {  
//        判断是否为空  
        if (heroNode.next == null) {  
            System.out.println("链表为空");  
            return;  
        }  
        //找到需要修改的节点,根据no修改.遍历  
        HeroNode temp = head.next;  
        boolean flag = false;  
        while (true) {  
            if (temp.next == null) {  
                break;  
            }  
            if (temp.no == heroNode.no) {  
                flag = true;  
                break;  
            }  
            temp = temp.next;  
        }  
        if (flag) {  
            temp.nickname = heroNode.nickname;  
            temp.name = heroNode.name;  
        } else {  
            System.out.println("未找到编号");  
        }  
    }  
  
    public void del(HeroNode heroNode) {  
        //        判断是否为空  
        if (heroNode.next == null) {  
            System.out.println("链表为空");  
            return;  
        }  
        HeroNode temp = head.next;  
        boolean flag = false;  
        while (true) {  
            if (temp.next == null) {  
                break;  
            }  
            if (temp.next.no == heroNode.no) {  
                flag = true;  
                break;  
            }  
            temp = temp.next;  
        }  
        if (flag) {  
            temp.next = temp.next.next;  
        } else {  
            System.out.println("要删除的不存在");  
        }  
    }  
  
    /**  
     * @param head 链表头节点  
     * @return 返回有效节点的个数  
     */  
    //获取单链表有效节点的个数(带头节点需要不统计头节点)  
    public static int getLength(HeroNode head) {  
        if (head.next == null) {  
            return 0;  
        }  
        int length = 0;  
  
//        定义辅助节点,不统计头节点  
        HeroNode cur = head.next;  
        while (cur != null) {  
            length++;  
            cur = cur.next;  
        }  
        return length;  
    }  
  
    //查找单链表的倒数第k个节点\  
//    1.编写方法接受head节点,同时接收index表示倒数第index个节点  
//    2.先把链表从头到尾遍历,length-index  
    public static HeroNode findLastIndexNode(HeroNode head, int index) {  
        if (head.next == null) {  
            return null;  
        }  
//        第一次遍历,得到链表长度  
        int length = getLength(head);  
//        第二次遍历length-index  
        if (index <= 0 || index > length) {  
            return null;  
        }  
        HeroNode temp = head.next;  
        for (int i = 0; i < length - index; i++) {  
            temp = temp.next;  
        }  
        return temp;  
    }  
  
    public static void reverseList(HeroNode head) {  
        if (head.next == null || head.next.next == null) {  
            return;  
        }  
        HeroNode cur = head.next;  
        HeroNode next = null;  
        HeroNode reverseHead = new HeroNode(0, "", "");  
//        遍历原来的链表  
        while (cur != null) {  
            next = cur.next;  
            cur.next = reverseHead.next;  
            reverseHead.next = cur;  
            cur = next;  
        }  
        head.next = reverseHead.next;  
    }  
  
    //    显示链表  
    public void list() {  
//        先判断链表是否为空  
        if (head.next == null) {  
            System.out.println("链表为空");  
            return;  
        }  
//        因为头节点不能动,因此需要辅助变量进行遍历  
        HeroNode temp = head.next;  
        while (true) {  
            if (temp == null) {  
                return;  
            }  
//            输出节点信息|  
            System.out.println(temp);  
//            temp后移  
            temp = temp.next;  
        }  
    }  
}  
  
  
//定义HeroNode,每个HeroNode对象就是一个节点  
class HeroNode {  
    public int no;  
    public String name;  
    public String nickname;  
    public HeroNode next;  
  
    //    构造器  
    public HeroNode(int no, String name, String nickname) {  
        this.name = name;  
        this.no = no;  
        this.nickname = nickname;  
    }  
  
    @Override  
    public String toString() {  
        return "HeroNode{" +  
                "no=" + no +  
                ", name='" + name + '\'' +  
                ", nickname='" + nickname + '\'' +  
                '}';  
    }  
}

4. 单链表反转的应用场景

4.1 数据库查询结果

在数据库查询结果返回时,常常使用链表结构,而在前端或后端中,可能需要反转链表以满足特定需求。

4.2 链表栈

在实现链表栈时,有时需要将栈的顺序反转,以便于一些特定操作。

5. 总结

单链表反转是一种常见而基础的链表操作,通过改变节点之间的链接方向,使得链表的尾部变为新的头部。实现方式有迭代法和递归法,各有特点。

  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...