Leetcode-.21合并两个有序链表

Leetcode
1.2k 词

迭代法是最直观、空间效率最高的方法。它的核心思想是创建一个新的链表，然后同时遍历 list1 和 list2，逐个比较节点的值，将较小的节点依次链接到新链表的末尾。

image.png

迭代法 (Iteration)

迭代法是最直观、空间效率最高的方法。它的核心思想是创建一个新的链表，然后同时遍历 list1 和 list2，逐个比较节点的值，将较小的节点依次链接到新链表的末尾。

关键技巧：哨兵节点 (Sentinel Node)

为了简化在空链表上添加第一个节点的操作，我们通常会创建一个“哨兵节点”（也叫虚拟头节点 dummy）。它不存储任何有效数据，只是作为新链表的临时头部。我们同时用一个 tail 指针来追踪新链表的最后一个节点，方便我们进行添加操作。

算法步骤：

  1. 初始化：

    • 创建一个哨兵节点 dummy = ListNode()。

    • 创建一个指针 tail = dummy，tail 将永远指向新链表的尾部。

  2. 主循环：当 list1 和 list2 都不为空时，进行循环：

    • 比较 list1.val 和 list2.val 的大小。

    • 如果 list1.val 更小，就将 list1 的当前节点链接到 tail.next，然后将 list1 指针后移一位。

    • 否则，将 list2 的当前节点链接到 tail.next，然后将 list2 指针后移一位。

    • 无论链接了哪个节点，都必须将 tail 指针后移一位 (tail = tail.next)，以确保它始终指向新链表的末尾。

  3. 处理剩余部分：循环结束后，list1 和 list2 最多只有一个还不为空。我们直接将这个非空的链表剩余的所有部分链接到 tail.next 即可。

  4. 返回结果：合并后的新链表的真正头节点是哨兵节点的下一个节点，即 dummy.next。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
# 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]:

        dummy=ListNode()

        tail=dummy

        p=list1

        q=list2

        while p and q:

            if p.val>=q.val:

                tail.next=q

                q=q.next

            else:

                tail.next=p

                p=p.next

            tail=tail.next

        if p==None:

            tail.next=q

        if q==None:

            tail.next=p

        return dummy.next