为什么这个链表问题中的虚拟节点会发生变化？(python3)

一尘不染

为什么这个链表问题中的虚拟节点会发生变化？(python3)

python

我已经阅读了几个解释并观看了 6 个 YouTube 视频，但仍然不明白这个 leetcode 问题的解决方案中发生了什么。有人可以用最简单的术语解释 dummy 和 cur 以及 dummy 和 cur.next 之间的关系吗？具体来说，我对以下内容感到困惑：

这是我所指的代码（我包含了一堆打印语句以尝试了解哪些代码行导致 dummy 更改）。

   cur = dummy = ListNode()
    iteration=1
    while list1 and list2:
        print("\n iteration=", iteration)
        print("list1.val & list2.val=",list1.val," & ",list2.val)
        print("****dummy=",dummy)

        if list1.val < list2.val:
            print("\n first block")
            cur.next = list1
            print("cur.next=",cur.next)
            print("****dummy=",dummy)
            list1, cur = list1.next, list1
            print("list1 & cur=",list1, " & \n", cur)
            print("****dummy=",dummy)
        else:
            print("\n second block")
            cur.next = list2 #cur.next=something --> dummy.next=something
            print("cur.next=", cur.next)
            print("****dummy=",dummy)
            list2, cur = list2.next, list2 #cur=something does not change dummy
            print("list2 & cur=",list2, " & \n ", cur)
            print("****dummy=",dummy)

        if list1 or list2:
            print("\n third block")
            cur.next = list1 if list1 else list2
            print("cur.next=",cur.next)
            print("****dummy=",dummy)



        iteration+=1
    print("\n cur=",cur)
    print("****dummy=",dummy)

    return dummy.next

这是第一次迭代的输出：

iteration= 1
list1.val & list2.val= 1  &  1
****dummy= ListNode{val: 0, next: None}

 second block
cur.next= ListNode{val: 1, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}}
****dummy= ListNode{val: 0, next: ListNode{val: 1, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}}}
list2 & cur= ListNode{val: 3, next: ListNode{val: 4, next: None}}  &
  ListNode{val: 1, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}}
****dummy= ListNode{val: 0, next: ListNode{val: 1, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}}}

 third block
cur.next= ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 4, next: None}}}
****dummy= ListNode{val: 0, next: ListNode{val: 1, next: ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 4, next: None}}}}}

好的，所以我从上面注意到，在第二个块中：cur.next=something, 设置dummy.next=something. 但是，cur=something, 并没有设置 dummy=something。为什么是这样？然后，在第三个块中，cur.next=something设置dummy.next.next =something（某物与 0,1 链接，而不是第二个块中的 0。为什么会这样？总的来说，我对整个“指针”的事情感到很困惑并且可以’不明白 & 如何与& cur&cur.next等相关。dummy``dummy.next``dummy.next.next

阅读 117

2022-06-12

共1个答案

一尘不染

这个问题的想法是创建一个对应于的“哨兵”节点dummy。这将是一个“虚拟”节点，表示新链表的头部，该链表将是执行合并后构建的“结果”链表。

# sentinel node
dummy = ListNode(-1)

# visual of `dummy` linked list
-1 -> None

该变量cur只是一个指向虚拟链表“头”的指针，我们将在合并list1和时使用它来插入新节点list2。Using表示在虚拟链表cur.next = some_node之后插入一个新节点。cur

# sentinel node
dummy = ListNode(-1)

# pointer to head of "dummy" linked list
cur = dummy

# both dummy and cur are positioned at the "head" node with value -1
-1 -> None

# inserting a new node to the "dummy" list would look like
cur.next = ListNode(2)

# cur = dummy at this point so cur is still at the first node -1
# the linked list would have 2 nodes and cur.next equals node 2
dummy
cur
-1 -> 2 -> None

# since cur is still at the "dummy" node equaling -1, we want to move `cur`
# to the newly inserted node, this allows `cur` to be ready 
# for another insertion at the correct position in the linked list
cur = cur.next

dummy  cur
-1   -> 2 -> None

# dummy.next would represent a linked list with a single node 2
2 -> None

下面是一种类似于您的逻辑的迭代方法，带有注释，以更好地说明我们如何在迭代两个链表时使用和cur继续移动节点指针将节点插入“虚拟”链表：list1``list2

# list1=[1,2,4]
# list2=[1,3,4]

# O(n+m) time and O(1) space
def mergeTwoLists(list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    # create a "dummy" node to represent 
    # resultant merged linked list
    dummy = ListNode(-1)

    # place cur pointer at head of dummy linked list
    cur = dummy

    # iterate both linked lists
    while list1 and list2:

        if list1.val <= list2.val:
            # insert node into the dummy list by updating
            # the "next" reference of `cur` to equal list1 node
            cur.next = list1

            # continue moving the list1 node to the "next" node in list1
            list1 = list1.next
        else:
            # insert node into the dummy list by updating
            # the "next" reference of `cur` to equal list2 node
            cur.next = list2

            # continue moving the list2 node to the "next" node in list2
            list2 = list2.next

        # keep moving the cur pointer as we insert to the dummy list
        cur = cur.next

    # there can be one value left to merge from one of the
    # two lists so insert the final node to complete the merge
    cur.next = list1 or list2

    # return dummy.next which skips the `dummy` node -1 and 
    # points to the new "head" of resultant merged list
    # -1 -> 1 -> 1 -> 2 -> 3 -> 4 -> 4 
    return dummy.next

2022-06-12