Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

关于单链表反转的一点整理

lukely 2019-08-13 23:46:00 阅读数:9 评论数:0 点赞数:0 收藏数:0

单链表的反转困扰了我好几天了。今天终于一通百通了,特地记录一下,免得以后又忘记了。脑子笨,只能靠这种办法了。

之前网上的一种做法是这样的:

 public void reversList(){
             Node pre = null;
             Node next = null;
             while (head != null) {
                 next = head.next;
                 head.next = pre;
                 pre = head;
                 head = next; 
             }
                 head = pre;
 }

 

 核心的代码就是这一段:

但实际上做种做法是错误的。我们先看看反转之后的情况。

一遍一遍遍历的过程是这样的。每一行就是一次遍历。

 Node [data=4, next=Node [data=3, next=Node [data=2, next=Node [data=1, next=Node [data=null, next=null]]]]]
 Node [data=3, next=Node [data=2, next=Node [data=1, next=Node [data=null, next=null]]]]
 Node [data=2, next=Node [data=1, next=Node [data=null, next=null]]]
 Node [data=1, next=Node [data=null, next=null]]
 Node [data=null, next=null]

 

这个实际上我没办法遍历,我是用最笨的办法一点一点还原出来的,如下:

 System.out.println(list.getHead());
 System.out.println(list.getHead().next);
 System.out.println(list.getHead().next.next);
 System.out.println(list.getHead().next.next.next);
 System.out.println(list.getHead().next.next.next.next);

 

我们再看看链表在反转之前是什么样子的,同样适用一样的笨办法:

 Node [data=null, next=Node [data=1, next=Node [data=2, next=Node [data=3, next=Node [data=4, next=null]]]]]
 Node [data=1, next=Node [data=2, next=Node [data=3, next=Node [data=4, next=null]]]]
 Node [data=2, next=Node [data=3, next=Node [data=4, next=null]]]
 Node [data=3, next=Node [data=4, next=null]]
 Node [data=4, next=null]

现在看来,反转前后,链表中有效的值只是大概相等而已,实际上并不一致。其在首尾节点上也是不一样的。

这种思路一开始是从head开始遍历开始反转的,但是其实head是一个指针节点,真正有效的节点是head.next,应该从这个开始遍历替换,所以真正应该遍历的当前节点其实是 head.next。而应该先保存的当前节点的下一个节点其实是 head.next.next。这是第一个错误。

第二个错误是:用来保存前一个节点的变量,不应该是Node  pre = null;而应该是Node pre = new Node(null)。这两种写法,完全是两个不同的东西。Node  pre = null 完全就是只有一个栈空间里的引用而已,根本没有指向堆里的空间,事实上这就不是一个对象。而Node pre = new Node(null)这种写法,是一种实打实的对象,是真正的引用指向了堆里面的空间了。所以当第二步  head.next = pre;(正确的是:head.next.next = pre.next)的时候,得到的结果就完全不一样了。如果pre=null;那就是把前一个有效节点都置为null了,这个对象就死了,真正要做的是断开前一个节点与后一个节点之间的指针连接,所以要置为null的是 pre.next,pre的指针域是null,而不是pre本身是null。这是两码事。这里我第一次看到网上的答案时,还不明白,为什么不可以直接直接Node  pre = null,这下才算是明白。

第一步第二步都错了之后,后面的步骤肯定也是错的了。

那为什么最后还可以得出一个对的假象呢?即:

Node [data=4, next=Node [data=3, next=Node [data=2, next=Node [data=1, next=Node [data=null, next=null]]]]]

最后得到的链表是这个,

这就是因为第二次循环之后,pre的next域,被恰好填充了对象,但是这个对象却是一个错误的对象如:

Node [data=1, next=Node [data=null, next=null]]

具体怎么错,以后慢慢研究吧。

正确的思路应该是,从head的next域指向的第一个有效节点开始遍历。可以直接在原来的链表上进行遍历替换。最后用反转之后的链表的第一个有效节点再接上head.next,这样head的指针域就指向了反转之后的链表。如下:

  public void reversList(){
          Node pre = new Node(null);
         //Node pre = null;错误写法
             Node next = null;
          
             while (head.next != null) {//从第一个有效节点开始遍历
                 next = head.next.next;//先记录当前节点的下一个节点
                 head.next.next = pre.next;//将当前节点的指针域置空
                 pre.next = head.next;//将下一节点的指针域,指向当前节点,完成节点交换
                 head.next = next;//往后移动
             }
            
                 head.next = pre.next;//最后把反转后的节点与头结点联系上。最终得到完整的反转之后的链表。
 }

 

或者也。可以新创建一个新的链表,然后遍历老链表后,把节点添加到新链表的第一个有效节点位置。最后返回新的链表,或者用新的链表覆盖head。也许这样比较容易理解:

public void reversList(){
             Node temp = head.next;//设置一个临时变量保存第一个有效节点
             Node newHead = new Node(null);//设置一个新的头结点
             Node next = null;//用于保存下一个节点
             
             while(temp != null){
                 next = temp.next;//保存当前节点的下一个节点
                 temp.next = newHead.next;//将当前节点的指针域置空
                 newHead.next = temp;//始终把当前节点插入到新链表的第一个有效节点的位置
                 temp = next;//向后移动一个节点
             }
            
             head = newHead;//最后把新的链表的头节点赋值给原节点的头结点,完成两个链表的合并
              //   head.next = newHead.next; 这种写法也是一个一样的效果,但是行为是不一样的行为。
        }        

 如果还有不对,欢迎指正。

版权声明
本文为[lukely]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/lukely/p/11349363.html