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

阳光穿透心脏的1/2处 2022-05-01 12:20 169阅读 0赞

[遍历法][Link 1]  
遍历法就是在链表遍历的过程中将指针顺序置换  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70]

//如何实现链表的反转
        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  
准备两个空结点 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结点  
进行循环…  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70 1]  
递归法  
总体来说，递归法是从最后一个Node开始，在弹栈的过程中将指针顺序置换的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70 2]  
递归实质上就是系统帮你压栈的过程，系统在压栈的时候会保留现场。  
我们来看是怎样的一个递归过程：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;
        }

@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;
            }
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70 3]

[Link 1]: https://www.cnblogs.com/keeya/p/9218352.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70]: /images/20220119/52a6475de98e4e72bff25449f39612ad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70 1]: /images/20220119/8d3a72a6b39843f0812ae7911028b4aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70 2]: /images/20220119/97813a43c9bf429eb07b29a8df994395.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70 3]: /images/20220119/3ce058bf76ea4eeda91a316072cecff8.png