链表:虚拟节点如何获取结果

huangapple go评论63阅读模式
英文:

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]) -&gt; Optional[ListNode]:
        x = ListNode()
        tail = x
        while list1 and list2:
            if  list1.val &lt;= 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.

huangapple
  • 本文由 发表于 2023年1月9日 06:48:20
  • 转载请务必保留本文链接:https://go.coder-hub.com/75051841.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定