英文:
Why does this 'b' linked list changed?
问题
我有两个链表:
'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;
}
英文:
I have 2 linked lists:
'a': 1->2->3->null
'b': 4->5->null
I want to merge them together as : 1->4->2->5->3->null
I write a function:
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;
}
what I think is to use a 'cur' to record each node in these 2 linked list 'a' and 'b'. Then these 2 linked lists 'a' and 'b' move to its next node. Then go to the next WHILE loop.
However, it's wrong. When I debug, in this first WHILE loop, when it finished this
cur.next = b;
it shows that variables will change as follow:
a: [1,5,4]
b: [5,4]
cur: [1,5,4]
I'm so confused why 'a' linked list will change to [1,5,4]? I think 'a' linked list won't change at this point, it keeps as [1,2,3].
--------But when I change WHILE loop as this following, it works:
while(a != null && b != null){
cur.next = a;
a=a.next;
cur = cur.next;
cur.next = b;
b=b.next;
cur = cur.next;
}
So my question is:
what's the difference between these two WHILE loop?
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;
}
答案1
得分: 0
当“cur”指向一个其下一个节点仍然需要的节点时,仍然无法赋值给next。
在方法末尾使用return;
是不必要的。
首先使用递归可能会有所帮助,先完成一小部分简单的工作,然后调用相同方法的其他实例来处理其余部分。
递归版本如下:
private ListNode merge(ListNode a, ListNode b) {
if (a == null) {
return b;
} else if (b == null) {
return a;
}
ListNode anext = a.next;
a.next = merge(b, a.next);
return a;
}
可以改写为迭代版本:
private ListNode merge(ListNode a, ListNode b) {
while (true) {
if (a == null) {
return b;
} else if (b == null) {
return a;
}
ListNode anext = a.next;
a.next = b;
a = b;
b = anext;
}
}
这种方法可以处理长度不同的链表,因此需要一个结果。
难点在于,与其执行a.next和b.next两步,而是调换了函数调用的参数。
你的版本将结果放在“a”中,并且要求两个链表具有相同的长度。
a
为空,而b
不为空是不可能的。
在你的第一个版本中,首先引入了一个0元素。
英文:
The problem that when cur
points to a node whose next is still needed you still cannot assign to next.
Tip at the end of a method return;
is not needed.
It may help to first use recursion, doing an easy bit of work, and call other instances of the same method for the rest.
A recursion would be:
private ListNode merge(ListNode a, ListNode b) {
if (a == null) {
return b;
} else if (b == null) {
return a;
}
ListNode anext = a.next;
a.next = merge(b, a.next);
return a;
}
which becomes iterative:
private ListNode merge(ListNode a, ListNode b) {
while (true) {
if (a == null) {
return b;
} else if (b == null) {
return a;
}
ListNode anext = a.next;
a.next = b;
a = b;
b = anext;
}
}
This handles lists with different lengths, and hence needs a result.
The difficult point is that instead of taking two steps a.next and b.next the call's arguments are switched.
Your version puts the results in a
and requires that both lists have the same length.
a
being null and b
not so would not be possible.
In your first version a 0 element is first introduced.
答案2
得分: 0
在你的 while 循环中存在一个 bug。对于一个正确的合并算法,你的循环不变式应该位于 while 循环的每次迭代结束时,ListNode
a 和 b 应该指向它们各自列表中的下一个元素。
while(a != null && b != null){
cur.next = a;
cur = cur.next;
cur.next = b;
cur = cur.next;
b = b.next;
a = a.next; // 你把 a 指向了列表 b 中的节点,这是错误的。
}
根据你的测试数据
列表 a:1 -> 2 -> 3
列表 b:4 -> 5
让我们在第一次迭代后检查你的 while 循环不变式
(i) a = a.next
将 a 设置为 b 中的第一个节点,即 4,但它应该指向其自己列表中的下一个元素 1 -> 2 -> 3
,即 2
这破坏了你的算法。
英文:
Yes there is a bug in your while loop . For a correct merge algorithm your loop invariant should be at the end of each iteration in the while loop ListNode
a and b should point to next element in their respective list .
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 .
}
From your test data
List a : 1 -> 2 -3
List b : 4 -> 5
Lets check the invariant of your while loop after 1st iteration
(i) a=a.next
sets a to first node in b i.e 4 whilst it should point to next element in its own list 1->2->3
i.e 2
This breaks your algorithm.
专注分享java语言的经验与见解,让所有开发者获益!
评论