英文:
Linkedlist : How does the dummy node gets the result
问题
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
x = ListNode()
tail = x
while list1 and list2:
if list1.val <= list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
if list1:
tail.next = list1
else:
tail.next = list2
return x.next
请注意,上面的代码部分已被翻译,不包括问题的其余部分。这段代码是一个合并两个有序链表的函数,将两个链表按照升序合并成一个新的链表。
关于您的疑问,当您在第一个if循环中将list1或list2的值添加到tail.next时,tail.next实际上指向了整个链表的头部,而不仅仅是一个单独的值。这是因为您正在构建一个新的链表,而不仅仅是一个包含单个值的节点。
所以,当您打印tail.next时,您看到了整个新链表的内容,而不仅仅是当前比较的单个值。这就是为什么您在打印输出中看到了多个值的原因。
希望这能帮助您理解为什么输出包含整个链表的内容而不仅仅是单个值。
英文:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
x = ListNode()
tail = x
while list1 and list2:
if list1.val <= list2.val:
tail.next = list1
# print(tail.next)
list1 = list1.next
else:
tail.next = list2
# print(tail.next)
list2 = list2.next
tail = tail.next
if list1:
tail.next = list1
# print(tail.next)
else:
tail.next = list2
# print(tail.next)
# print(x.next)
return x.next
Inputs
list1 =
[1,2,4]
list2 =
[1,3,4]
Output for the above code:
Expected solution and my output is similar
[1,1,2,3,4,4]
Print : However I do not understand the below part where it prints the values inside the listnode
ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 4, next: None}}}
ListNode{val: 1, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}}
ListNode{val: 2, next: ListNode{val: 4, next: None}}
ListNode{val: 3, next: ListNode{val: 4, next: None}}
ListNode{val: 4, next: None}
ListNode{val: 4, next: None}
ListNode{val: 1, next: ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: ListNode{val: 4, next: ListNode{val: 4, next: None}}}}}}
When I print the code at first if loop I get the tail.next value as the values inside the list1. Similarly if you see the print output it shows all the tail.next values, however according to my logic the tail.next value should only contain the value of the list which I am comparing.
For example: in first case I compare 1 vs 1 and the output should be 1.
However if I print tail.next I see that the values are 1,2,4. I don't understand why???
答案1
得分: 1
tail.next
不是一个孤立的节点。它有自己的 next
属性。
这是你提供的示例的简要可视化:
在函数开始时,创建了虚拟节点 x
(默认值为0),并且 tail
也引用了它:
list1
│
┌─┴──────────┐ ┌────────────┐ ┌────────────┐
│ val: 1 │ │ val: 2 │ │ val: 4 │
│ next: ──────────┤ next: ──────────┤ next: None │
x └────────────┘ └────────────┘ └────────────┘
│
┌─┴──────────┐
│ val: 0 │
│ next: None │
└─┬──────────┘
│
tail ┌────────────┐ ┌────────────┐ ┌────────────┐
│ val: 1 │ │ val: 3 │ │ val: 4 │
│ next: ──────────┤ next: ──────────┤ next: None │
└─┬──────────┘ └────────────┘ └────────────┘
│
list2
在循环的第一次迭代中,if
条件为真,因此执行 tail.next = list1
,这会改变虚拟节点的 next
属性:
list1
│
┌─┴──────────┐ ┌────────────┐ ┌────────────┐
│ val: 1 │ │ val: 2 │ │ val: 4 │
┌──┤ next: ──────────┤ next: ──────────┤ next: None │
x │ └────────────┘ └────────────┘ └────────────┘
│ │
┌─┴──────────┐│
│ val: 0 ││
│ next: ──────┘
└─┬──────────┘
│
tail ┌────────────┐ ┌────────────┐ ┌────────────┐
│ val: 1 │ │ val: 3 │ │ val: 4 │
│ next: ──────────┤ next: ──────────┤ next: None │
└─┬──────────┘ └────────────┘ └────────────┘
│
list2
正如你可以看到的,tail
已经添加到了 list1
前面,而 list1
本身具有一系列嵌套的节点引用。因此,现在通过 tail
也可以访问这些节点。
按照相同的逻辑,打印 list1
将输出一个包含1、2和4值的嵌套结构,打印 tail
将输出一个包含0、1、2和4值的嵌套结构。
另请参阅Merging two linked lists - how does the dummy node get updated?以详细了解合并算法的其余部分如何完成这项工作。
英文:
tail.next
is not an isolated node. It has a next
attribute of its own.
Here is a small visualisation of the example you have given:
At the start of the function, the dummy node x
is created (with default value 0), and also tail
gets a reference to it:
list1
│
┌─┴──────────┐ ┌────────────┐ ┌────────────┐
│ val: 1 │ │ val: 2 │ │ val: 4 │
│ next: ──────────┤ next: ──────────┤ next: None │
x └────────────┘ └────────────┘ └────────────┘
│
┌─┴──────────┐
│ val: 0 │
│ next: None │
└─┬──────────┘
│
tail ┌────────────┐ ┌────────────┐ ┌────────────┐
│ val: 1 │ │ val: 3 │ │ val: 4 │
│ next: ──────────┤ next: ──────────┤ next: None │
└─┬──────────┘ └────────────┘ └────────────┘
│
list2
In the first iteration of the loop, the if
condition is true, so tail.next = list1
gets executed, which mutates the dummy node's next
attribute:
list1
│
┌─┴──────────┐ ┌────────────┐ ┌────────────┐
│ val: 1 │ │ val: 2 │ │ val: 4 │
┌──┤ next: ──────────┤ next: ──────────┤ next: None │
x │ └────────────┘ └────────────┘ └────────────┘
│ │
┌─┴──────────┐│
│ val: 0 ││
│ next: ──────┘
└─┬──────────┘
│
tail ┌────────────┐ ┌────────────┐ ┌────────────┐
│ val: 1 │ │ val: 3 │ │ val: 4 │
│ next: ──────────┤ next: ──────────┤ next: None │
└─┬──────────┘ └────────────┘ └────────────┘
│
list2
And as you can see tail
has been prefixed to list1
, which itself has a chain of nested node references. By consequence those nodes now also are reachable through tail
.
By the same logic that printing list1
will output a nested structure containing 1, 2, and 4 values, printing tail
will output a nested structure containing 0, 1, 2, and 4 values.
See also Merging two linked lists - how does the dummy node get updated? for a detailed explanation of how the rest of the merge algorithm does the job.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论