时间戳

首页 > 解决方案 > 为什么这个'b'链表改变了？

java - 为什么这个'b'链表改变了？

问题描述

我有 2 个链表：

'a': 1->2->3->null

'b': 4->5->null

我想将它们合并为：1->4->2->5->3->null

我写了一个函数：

    private void merge(ListNode a, ListNode b){
        ListNode cur = new ListNode(0);
        
        while(a != null && b != null){
            cur.next = a;
            cur = cur.next;
     
            cur.next = b;
            cur = cur.next;
            
            b=b.next;
            a=a.next;
        }
        if(a==null && b==null) return;
        else if(a==null){
            cur.next = b;
        }else if(b==null){
            cur.next = a;
        }
        return;
    }

我认为是使用'cur'来记录这两个链表'a'和'b'中的每个节点。然后这两个链表“a”和“b”移动到下一个节点。然后进入下一个 WHILE 循环。

然而，这是错误的。当我调试时，在第一个 WHILE 循环中，当它完成时

cur.next = b;

它表明变量将发生如下变化：

a: [1,5,4]
b: [5,4]
cur: [1,5,4]

我很困惑为什么'a'链表会变成[1,5,4]？我认为'a'链表此时不会改变，它保持为[1,2,3]。

--------但是当我将 WHILE 循环更改如下时，它可以工作：

    while(a != null && b != null){
            cur.next = a;
            a=a.next;
            cur = cur.next;
            cur.next = b;
            b=b.next;
            cur = cur.next;
        }

所以我的问题是：这两个 WHILE 循环有什么区别？

    while(a != null && b != null){
            cur.next = a;
            a=a.next;
            cur = cur.next;

            cur.next = b;
            b=b.next;
            cur = cur.next;
        }

while(a != null && b != null){
            cur.next = a;
            cur = cur.next;
     
            cur.next = b;
            cur = cur.next;
            
            b=b.next;
            a=a.next;
        }

标签： javalinked-list

解决方案

是的，您的 while 循环中有一个错误。对于正确的合并算法，您的循环不变量应该在 while 循环中的每次迭代结束时，ListNodea 和 b 应该指向它们各自列表中的下一个元素。

while(a != null && b != null){
            cur.next = a;
            cur = cur.next;
     
            cur.next = b;
            cur = cur.next;
            
            b=b.next; 
            a=a.next; // you are making a point to node in list b , which is wrong .
        }

根据您的测试数据

列表 a : 1 -> 2 -3 列表 b : 4 -> 5

让我们在第一次迭代后检查 while 循环的不变量

(i) a=a.next将 a 设置为 b 中的第一个节点，即 4，而它应该指向它自己的列表中的下一个元素，1->2->3即 2

这打破了你的算法。

推荐阅读