英文:
The below code causing an infinite loop eventhough i didn't use head node in the while loop
问题
在curr_node1和curr_node2都变为null后，循环应该已经终止，但实际上它导致了一个无限循环。这是因为您在循环中没有正确地处理链表的结尾。当其中一个链表到达末尾时，您仍然在尝试访问它的next属性，这导致了无限循环。
简单来说，问题在于您没有正确地处理链表的结束条件，导致了无限循环。
英文:
After curr_node1 and curr_node2 becomes null while loop should have been terminated but instead it is causing an infinite loop. What is the reason of this can someone please explain it to me in simple words as I am a newbie.
class Node1:
def __init__(self, data):
self.data=data
self.next=None
class Node2:
def __init__(self, data):
self.data=data
self.next=None
def merge_sorted_ll(list1,list2):
head=list1
head.next=list2
head=head.next
curr_node1=list1
curr_node2=list2
while curr_node1 and curr_node2:
curr_node1=curr_node1.next
curr_node2=curr_node2.next
head.next=curr_node1
head.next.next=curr_node2
head=head.next.next
return head
list2=Node2(10)
list2.next=Node2(21)
list2.next.next=Node2(31)
list1=Node1(10)
list1.next=Node1(20)
list1.next.next=Node1(30)
merge_sorted_ll(list1,list2)
I want to merge two sorted linkedlist and please don't give me a corrected version of code. I know the logic is wrong but I just wanted to know why my code causing an infinite loop.
答案1
得分: 1
以下是您要翻译的内容的翻译：
可能会有助于在纸上绘制链接列表，并绘制代码对它们带来的每个更改。
当您的函数开始时，名称list1和list2引用如下结构。我还包括head=list1的结果：
list1 head
┌─┴───────┴──┐ ┌────────────┐ ┌────────────┐
│ data: 10 │ │ data: 20 │ │ data: 30 │
│ next: ────────────┤ next: ────────────┤ next: None │
└────────────┘ └────────────┘ └────────────┘
list2
┌─┴──────────┐ ┌────────────┐ ┌────────────┐
│ data: 10 │ │ data: 21 │ │ data: 31 │
│ next: ────────────┤ next: ────────────┤ next: None │
└────────────┘ └────────────┘ └────────────┘
然后引入了第一个问题，因为head.next=list2覆盖了原始的next引用，因此我们失去了第一个列表的其余部分：
list1 head (no more reference to this)
┌─┴───────┴──┐ ┌────────────┐ ┌────────────┐
│ data: 10 │ │ data: 20 │ │ data: 30 │
│ next: ─┐ │ │ next: ────────────┤ next: None │
└────────│───┘ └────────────┘ └────────────┘
│
list2 │
┌─┴──────┴───┐ ┌────────────┐ ┌────────────┐
│ data: 10 │ │ data: 21 │ │ data: 31 │
│ next: ────────────┤ next: ────────────┤ next: None │
└────────────┘ └────────────┘ └────────────┘
接下来对名称head，curr_node1和curr_node2的三个赋值导致了以下情况（我省略了我们失去引用的节点）：
list1 curr_node1
┌─┴───────┴──┐
│ data: 10 │
│ next: ─┐ │
└────────│───┘
│
list2 │
┌─┴──────┴───┐ ┌────────────┐ ┌────────────┐
│ data: 10 │ │ data: 21 │ │ data: 31 │
│ next: ────────────┤ next: ────────────┤ next: None │
└─┬───────┬──┘ └────────────┘ └────────────┘
head curr_node2
现在循环开始。让我们看看每次迭代...
迭代 1
循环进入，curr_node1和curr_node2沿着它们的next链接移动一步：
list1
┌─┴──────────┐
│ data: 10 │
│ next: ─┐ │
└────────│───┘
│
list2 │
┌─┴──────┴───┐ ┌────────────┐ ┌────────────┐
│ data: 10 │ │ data: 21 │ │ data: 31 │
│ next: ────────────┤ next: ────────────┤ next: None │
└─┬───────┬──┘ └───┬────────┘ └────────────┘
head curr_node1 curr_node2
现在下一个问题出现了：赋值head.next=curr_node1将创建一个循环，因为head和curr_node1引用相同的节点：
list1
┌─┴──────────┐
│ data: 10 │
│ next: ─┐ │
└────────│───┘
│
list2 │ ┌───┐
┌─┴──────┴─┴─┐ │ ┌────────────┐ ┌────────────┐
│ data: 10 │ │ │ data: 21 │ │ data: 31 │
│ next: ───────┘ │ next: ────────────┤ next: None │
└─┬───────┬──┘ └───┬────────┘ └────────────┘
head curr_node1 curr_node2
因此，head.next.next与head相同。使用head.next.next=curr_node2将恢复链接：
list1
┌─┴──────────┐
│ data: 10 │
│ next: ─┐ │
└────────│───┘
│
list2 │
┌─┴──────┴───┐ ┌────────────┐ ┌────────────┐
│ data: 10 │ │ data: 21 │ │ data: 31 │
│ next: ────────────┤ next: ────────────┤ next: None │
└─┬───────┬──┘ └───┬────────┘ └────────────┘
head curr_node1 curr_node2
使用head=head.next.next我们得到：
list1
┌─┴──────────┐
│ data: 10 │
│ next: ─┐ │
└────────│───┘
│
list2 │
┌─┴──────┴───┐ ┌────────────┐ ┌────────────┐
│ data: 10 │ │ data:
<details>
<summary>英文:</summary>
It may help to draw the linked lists on paper and draw each change that the code brings to them.
When your function starts, the names `list1` and `list2` are referencing the structures below. I also include the result of `head=list1`:
```none
list1 head
┌─┴───────┴──┐ ┌────────────┐ ┌────────────┐
│ data: 10 │ │ data: 20 │ │ data: 30 │
│ next: ────────────┤ next: ────────────┤ next: None │
└────────────┘ └────────────┘ └────────────┘
list2
┌─┴──────────┐ ┌────────────┐ ┌────────────┐
│ data: 10 │ │ data: 21 │ │ data: 31 │
│ next: ────────────┤ next: ────────────┤ next: None │
└────────────┘ └────────────┘ └────────────┘
Then the first problem is introduced, because head.next=list2 overwrites the original next reference, and so we lose the rest of the first list:
list1 head (no more reference to this)
┌─┴───────┴──┐ ┌────────────┐ ┌────────────┐
│ data: 10 │ │ data: 20 │ │ data: 30 │
│ next: ─┐ │ │ next: ────────────┤ next: None │
└────────│───┘ └────────────┘ └────────────┘
│
list2 │
┌─┴──────┴───┐ ┌────────────┐ ┌────────────┐
│ data: 10 │ │ data: 21 │ │ data: 31 │
│ next: ────────────┤ next: ────────────┤ next: None │
└────────────┘ └────────────┘ └────────────┘
The next three assignments to names head, curr_node1 and curr_node2 lead to this (I omit the nodes to which we lost any reference):
list1 curr_node1
┌─┴───────┴──┐
│ data: 10 │
│ next: ─┐ │
└────────│───┘
│
list2 │
┌─┴──────┴───┐ ┌────────────┐ ┌────────────┐
│ data: 10 │ │ data: 21 │ │ data: 31 │
│ next: ────────────┤ next: ────────────┤ next: None │
└─┬───────┬──┘ └────────────┘ └────────────┘
head curr_node2
Now the loop starts. Let's look at each iteration...
Iteration 1
The loop enters, and curr_node1 and curr_node2 move one step along their next links:
list1
┌─┴──────────┐
│ data: 10 │
│ next: ─┐ │
└────────│───┘
│
list2 │
┌─┴──────┴───┐ ┌────────────┐ ┌────────────┐
│ data: 10 │ │ data: 21 │ │ data: 31 │
│ next: ────────────┤ next: ────────────┤ next: None │
└─┬───────┬──┘ └───┬────────┘ └────────────┘
head curr_node1 curr_node2
Now the next problem occurs: the assignment head.next=curr_node1 will create a cycle, because head and curr_node1 reference the same node:
list1
┌─┴──────────┐
│ data: 10 │
│ next: ─┐ │
└────────│───┘
│
list2 │ ┌───┐
┌─┴──────┴─┴─┐ │ ┌────────────┐ ┌────────────┐
│ data: 10 │ │ │ data: 21 │ │ data: 31 │
│ next: ───────┘ │ next: ────────────┤ next: None │
└─┬───────┬──┘ └───┬────────┘ └────────────┘
head curr_node1 curr_node2
As a consequence, head.next.next is the same as just head. With head.next.next=curr_node2 the link is restored again:
list1
┌─┴──────────┐
│ data: 10 │
│ next: ─┐ │
└────────│───┘
│
list2 │
┌─┴──────┴───┐ ┌────────────┐ ┌────────────┐
│ data: 10 │ │ data: 21 │ │ data: 31 │
│ next: ────────────┤ next: ────────────┤ next: None │
└─┬───────┬──┘ └───┬────────┘ └────────────┘
head curr_node1 curr_node2
With head=head.next.next we get:
list1
┌─┴──────────┐
│ data: 10 │
│ next: ─┐ │
└────────│───┘
│
list2 │
┌─┴──────┴───┐ ┌────────────┐ ┌────────────┐
│ data: 10 │ │ data: 21 │ │ data: 31 │
│ next: ────────────┤ next: ────────────┤ next: None │
└────────┬───┘ └───────┬────┘ └────┬───────┘
curr_node1 curr_node2 head
Iteration 2
The two curr references are moved one step again, and so we get:
list1
┌─┴──────────┐
│ data: 10 │
│ next: ─┐ │
└────────│───┘
│
list2 │
┌─┴──────┴───┐ ┌────────────┐ ┌────────────┐
│ data: 10 │ │ data: 21 │ │ data: 31 │
│ next: ────────────┤ next: ────────────┤ next: None │
└────────────┘ └──────┬─────┘ └──┬─────┬───┘
curr_node1 curr_node2 head
Now head.next=curr_node1 will create a greater cycle:
list1
┌─┴──────────┐
│ data: 10 │
│ next: ─┐ │
└────────│───┘
│
list2 │ ┌─────────────────────┐
┌─┴──────┴───┐ ┌────────┴───┐ ┌──────────│─┐
│ data: 10 │ │ data: 21 │ │ data: 31 │ │
│ next: ────────────┤ next: ────────────┤ next: ───┘ │
└────────────┘ └──────┬─────┘ └──┬─────┬───┘
curr_node1 curr_node2 head
And the next head.next.next=curr_node2 assignment will do nothing, because the references at both sides of the = are already equal. Also head=head.next.next will not accomplish anything for the same reason.
Iteration 3
This iteration starts with a state where the list has a cycle with size 2, and so the first two assignments will swap the two cur references:
list1
┌─┴──────────┐
│ data: 10 │
│ next: ─┐ │
└────────│───┘
│
list2 │ ┌─────────────────────┐
┌─┴──────┴───┐ ┌────────┴───┐ ┌──────────│─┐
│ data: 10 │ │ data: 21 │ │ data: 31 │ │
│ next: ────────────┤ next: ────────────┤ next: ───┘ │
└────────────┘ └──────┬─────┘ └──┬─────┬───┘
curr_node2 curr_node1 head
head.next=curr1 will create the self-reference again, and head.next.next=curr_node2 will revert that change. head=head.next.next will not accomplish anything: the structure of the linked list at the end of this iteration is the same as when the iteration started.
Only the two cur references got swapped. The fourth iteration will do the opposite swap, ...etc, and so we have an infinite loop.
答案2
得分: 0
在你的 while 循环中，while curr_node1 and curr_node2，你没有设置退出条件。当前，这个 while 循环一直在检查这两个对象是否存在，而它们存在，因此它会一直循环运行。你需要在循环中设置一些内容来跳出循环，可以通过使条件为假或在某个地方包含一个 break 语句来实现。
英文:
In your while loop, while curr_node1 and curr_node2, you don't have an exit condition. Right now, the while loop is checking to see if those two objects exist, which they do, so it will always run in a loop. You need to have something to break out of that loop, either by making the conditional false or including a break statement somewhere.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论