按排序顺序合并 2 个链表

Question

合并两个排序的链表并return它作为一个排序的列表。该列表应通过将前两个列表的节点拼接在一起来制作。

我们有 l1:

ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 4, next: None}}}

和 l2:

ListNode{val: 1, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}}

我使用以下代码合并它们：

# 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, l1: ListNode, l2: ListNode) -> ListNode:
        print(l1)
        print(l2)
        out = ListNode(-1)
        temp = out
        while l1 and l2:
            if (l1.val < l2.val):
                temp.next = l1
                l1 = l1.next
            else:
                temp.next = l2
                l2 = l2.next
            temp = temp.next
        print(out)

结果是这样的：

ListNode{val: -1, next: ListNode{val: 1, next: ListNode{val: 1, next: ListNode{val: 2, next: ListNode{val: 3, next: ListNode{val: 4, next: None}}}}}}

我的问题是 out 是如何更新的？

Answer 1

out 在 while 循环的第一次迭代中发生变异。

想象一下可能会有所帮助。

就在循环开始之前，我们创建了一个虚拟节点（值为 -1）并用 out 和 temp:

引用它

                   l1
                   ↓
                 ┌────────────┐    ┌────────────┐    ┌────────────┐
                 │ data: 1    │    │ data: 2    │    │ data: 4    │
                 │ next: ────────> │ next: ────────> │ next: None │
 out             └────────────┘    └────────────┘    └────────────┘
  ↓
┌────────────┐
│ data: -1   │
│ next: None │
└────────────┘
  ↑
 temp            ┌────────────┐    ┌────────────┐    ┌────────────┐
                 │ data: 1    │    │ data: 3    │    │ data: 4    │
                 │ next: ────────> │ next: ────────> │ next: None │
                 └────────────┘    └────────────┘    └────────────┘
                   ↑
                   l2

在第一次迭代中，我们进入 else 块，其中 temp 是 变异的 。由于 temp 和 out 引用同一个对象，这会改变 out.

                   l1
                   ↓
                 ┌────────────┐    ┌────────────┐    ┌────────────┐
                 │ data: 1    │    │ data: 2    │    │ data: 4    │
                 │ next: ────────> │ next: ────────> │ next: None │
 out             └────────────┘    └────────────┘    └────────────┘
  ↓
┌────────────┐
│ data: -1   │
│ next: ──────┐
└────────────┘│
  ↑           │
 temp         │  ┌────────────┐    ┌────────────┐    ┌────────────┐
              │  │ data: 1    │    │ data: 3    │    │ data: 4    │
              └> │ next: ────────> │ next: ────────> │ next: None │
                 └────────────┘    └────────────┘    └────────────┘
                   ↑
                   l2

这次更新后，l2 和 temp 都被“移动”以指代他们的继任者。第一次迭代到此结束：

                   l1
                   ↓
                 ┌────────────┐    ┌────────────┐    ┌────────────┐
                 │ data: 1    │    │ data: 2    │    │ data: 4    │
                 │ next: ────────> │ next: ────────> │ next: None │
 out             └────────────┘    └────────────┘    └────────────┘
  ↓
┌────────────┐
│ data: -1   │
│ next: ──────┐
└────────────┘│
              │
              │  ┌────────────┐    ┌────────────┐    ┌────────────┐
              │  │ data: 1    │    │ data: 3    │    │ data: 4    │
              └> │ next: ────────> │ next: ────────> │ next: None │
                 └────────────┘    └────────────┘    └────────────┘
                   ↑                 ↑
                  temp               l2

我们真的不必继续执行该算法，因为从现在开始 out 不会再次发生变异：这项工作已经完成。但是，让我们再继续一次迭代（第二次迭代）。我们进入 if 块，temp 再次发生变异（但这一次，它不是 out 的同义词）：

                   l1
                   ↓
                 ┌────────────┐    ┌────────────┐    ┌────────────┐
                 │ data: 1    │    │ data: 2    │    │ data: 4    │
              ┌> │ next: ────────> │ next: ────────> │ next: None │
 out          │  └────────────┘    └────────────┘    └────────────┘
  ↓           └────────────────┐
┌────────────┐                 │
│ data: -1   │                 │
│ next: ──────┐                │
└────────────┘│                │
              │                │
              │  ┌────────────┐│   ┌────────────┐    ┌────────────┐
              │  │ data: 1    ││   │ data: 3    │    │ data: 4    │
              └> │ next: ──────┘   │ next: ────────> │ next: None │
                 └────────────┘    └────────────┘    └────────────┘
                   ↑                 ↑
                  temp               l2

...并且 l1 和 temp 都移至他们的继任者：

                  temp               l1
                   ↓                 ↓
                 ┌────────────┐    ┌────────────┐    ┌────────────┐
                 │ data: 1    │    │ data: 2    │    │ data: 4    │
              ┌> │ next: ────────> │ next: ────────> │ next: None │
 out          │  └────────────┘    └────────────┘    └────────────┘
  ↓           └────────────────┐
┌────────────┐                 │
│ data: -1   │                 │
│ next: ──────┐                │
└────────────┘│                │
              │                │
              │  ┌────────────┐│   ┌────────────┐    ┌────────────┐
              │  │ data: 1    ││   │ data: 3    │    │ data: 4    │
              └> │ next: ──────┘   │ next: ────────> │ next: None │
                 └────────────┘    └────────────┘    └────────────┘
                                     ↑
                                     l2

继续这样，temp 将保留正在连接的结果列表的尾部。在最后一次迭代之后，我们将得到：

                                                       l1
                                                       ↓
                 ┌────────────┐    ┌────────────┐    ┌────────────┐
                 │ data: 1    │    │ data: 2    │    │ data: 4    │
              ┌> │ next: ────────> │ next: ──────┐   │ next: None │
 out          │  └────────────┘    └────────────┘│   └────────────┘
  ↓           └────────────────┐ ┌───────────────┘
┌────────────┐                 │ │                                
│ data: -1   │                 │ │                                
│ next: ──────┐                │ │                                
└────────────┘│                │ │                                
              │                │ │                                
              │  ┌────────────┐│ │ ┌────────────┐    ┌────────────┐
              │  │ data: 1    ││ │ │ data: 3    │    │ data: 4    │
              └> │ next: ──────┘ └>│ next: ────────> │ next: None │
                 └────────────┘    └────────────┘    └────────────┘
                                                       ↑                
                                                      temp

这项工作尚未完全完成，因为您发布的代码段中缺少一些代码。当 while 循环退出时，l1 或 l2 之一将不是 None，这表示仍然需要附加到结果列表的部分。由于 temp 指的是结果列表的当前尾部，我们应该将其 next 引用设置为 l1 或 l2 —— 以不是 None 的那个为准。

所以代码在循环后应该有类似下面的语句：

temp.next = l1 or l2

...结果是：

                                                       l1
                                                       ↓
                 ┌────────────┐    ┌────────────┐    ┌────────────┐
                 │ data: 1    │    │ data: 2    │    │ data: 4    │
              ┌> │ next: ────────> │ next: ──────┐ ┌>│ next: None │
 out          │  └────────────┘    └────────────┘│ │ └────────────┘
  ↓           └────────────────┐ ┌───────────────┘ └───────────────┐
┌────────────┐                 │ │                                 │
│ data: -1   │                 │ │                                 │
│ next: ──────┐                │ │                                 │
└────────────┘│                │ │                                 │
              │                │ │                                 │
              │  ┌────────────┐│ │ ┌────────────┐    ┌────────────┐│
              │  │ data: 1    ││ │ │ data: 3    │    │ data: 4    ││
              └> │ next: ──────┘ └>│ next: ────────> │ next: ──────┘
                 └────────────┘    └────────────┘    └────────────┘
                                                       ↑                
                                                      temp

最后，函数应该 return 结果。由于 out 指的是一个虚拟节点，我们不应该只是 return out，而是 out.next:

return out.next

returned 列表引用将指向此：

           ┌────────────┐    ┌────────────┐    ┌────────────┐
           │ data: 1    │    │ data: 2    │    │ data: 4    │
        ┌> │ next: ────────> │ next: ──────┐ ┌>│ next: None │
        │  └────────────┘    └────────────┘│ │ └────────────┘
        └────────────────┐ ┌───────────────┘ └───────────────┐
                         │ │                                 │
           ┌────────────┐│ │ ┌────────────┐    ┌────────────┐│
           │ data: 1    ││ │ │ data: 3    │    │ data: 4    ││
returned → │ next: ──────┘ └>│ next: ────────> │ next: ──────┘
           └────────────┘    └────────────┘    └────────────┘

我希望这能说明问题。

Answer 2

如果有帮助，您甚至不需要任何临时节点。您可以重新链接现有节点，这会使其变得更加简单：

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not (l1 and l2):
            return l1 or l2
        if l2.val < l1.val:
            l1, l2 = l2, l1
        l1.next = self.mergeTwoLists(l1.next, l2)
        return l1

按排序顺序合并 2 个链表

merge 2 linked lists in sorted order

python

sorting

merge

linked-list