理解单链表的反转(java实现)_java链表反转

遍历法
遍历法就是在链表遍历的过程中将指针顺序置换

//如何实现链表的反转
    public static Node ReverseIteratively(Node head){
        Node pre = null;
        Node next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
1
2
3
4
5
6
7
8
9
10
11
12

依旧是1->2->3->4
准备两个空结点 pre用来保存先前结点、next用来做临时变量
在头结点node遍历的时候此时为1结点
next = 1结点.next(2结点)
1结点.next=pre(null)
pre = 1结点
node = 2结点
进行下一次循环node=2结点
next = 2结点.next(3结点)
2结点.next=pre(1结点)=>即完成2->1
pre = 2结点
node = 3结点
进行循环…

递归法
总体来说，递归法是从最后一个Node开始，在弹栈的过程中将指针顺序置换的。

递归实质上就是系统帮你压栈的过程，系统在压栈的时候会保留现场。
我们来看是怎样的一个递归过程：1->2->3->4
程序到达Node newHead = reverse(head.next);时进入递归
我们假设此时递归到了3结点，此时head=3结点，temp=3结点.next(实际上是4结点)
执行Node newHead = reverse(head.next);传入的head.next是4结点，返回的newHead是4结点。
接下来就是弹栈过程了
程序继续执行 temp.next = head就相当于4->3
head.next = null 即把3结点指向4结点的指针断掉。
返回新链表的头结点newHead

//递归实质上就是系统帮你压栈的过程，系统在压栈的时候会保留现场
    public Node reverse(Node head) {
        //递归
        if (null == head ||null  == head.next)
            return head;
        Node temp = head.next;
        Node newHead = reverse(head.next);
        temp.next = head;
        head.next = null;
        return newHead;
    }
1
2
3
4
5
6
7
8
9
10
11

@Test
    public void testCase() {
        LinkedList list = new LinkedList();
        System.out.println("测试头插法");
        list.addNodeHead(4);
        list.addNodeHead(3);
        list.display();
        list.addNodeHead(2);
        list.addNodeHead(1);
        /*list.display();
        list.addNodeTail(4);
        list.display();
        System.out.println("测试某个位置删除法");
        list.deleteNode(3);
        list.display();
        System.out.println("测试删除重复数据前");
        list.addNodeHead(1);
        list.display();
        System.out.println("测试删除重复数据");
        list.deleteDuplecate1(list.head);
        list.display();
        System.out.println("测试删除重复数据1");
        list.addNodeIndex(2,1);
        list.display();
        list.deleteDuplecate(list.head);*/
        list.display();
        System.out.println("链表的反转");
        //Node node = LinkedList.ReverseIteratively(list.head);
        Node node1 = list.reverse(list.head);
        while (node1 != null){
            System.out.println(node1.data);
            node1 = node1.next;
        }
    }
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