目录

单向链表逆序

要求:在一个原有的单链表上执行逆序操作

处理思路

  1. 定义一个反转节点
  2. 遍历原链表,每遍历一个节点都将该节点指向反转节点的第一个元素,跟"头插法"一样
  3. 将原链表的头节点指向反转节点的第一个元素。 下面这张图可以很好地说明这个过程 https://gitee.com/lienhui68/picStore/raw/master/null/2.png

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public void reverse() {
        // 如果没有元素或只有一个元素无需反转
        if (head.next == null || head.next.next == null) {
            System.out.println("无需反转");
            return;
        }
        // 定义一个反转节点
        Node reverse = new Node();
        // 定义一个当前变量,用来遍历
        Node cur = head.next;
        // 定义next节点变量用来保存当前节点的下一个节点
        Node next;

        while (cur != null) {
            // 1. 保存当前节点的下一个节点
            next = cur.next;
            // 2. 将当前节点指向反转节点的第一个元素
            cur.next = reverse.next;
            // 3. 将反转节点指向当前节点
            reverse.next = cur;
            // 4. 遍历下一个节点
            cur = next;
        }

        head.next = reverse.next;

    }

    public static void main(String[] args) {
        SingleLinkedList list = new SingleLinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.reverse();
        System.out.println("========反转后的链表========");
        list.display();
    }

运行结果 https://gitee.com/lienhui68/picStore/raw/master/null/20200616155920.png