2.0021. 合并两个有序链表

2.1 题目大意

描述：给定两个升序链表的头节点 list1 和 list2。

要求：将其合并为一个升序链表。

说明：

  • 两个链表的节点数目范围是 。
  • list1 和 list2 均按 非递减顺序 排列

示例：

img

1
2
3
4
5
6
 输入：list1 = [1,2,4], list2 = [1,3,4]
 输出：[1,1,2,3,4,4]
 
 
 输入：list1 = [], list2 = []
 输出：[]

题解：

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
 # 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，它的 next 最后会指向合并后的链表头
         dummy = ListNode(-1)
         current = dummy
 
         # 遍历两个链表，哪个值小就接到 current 后面
         while list1 and list2:
             if list1.val <= list2.val:
                 current.next = list1
                 list1 = list1.next
             else:
                 current.next = list2
                 list2 = list2.next
             current = current.next  # 移动 current 指针
 
         # 把剩余的链表接上（最多只有一个不为 None）
         current.next = list1 if list1 else list2
 
         # 返回合并后的链表头
         return dummy.next
 

**在新建链表的时候，我们可以选择用哑节点加指针的方式来简化代码逻辑。哑节点是一个不存储实际数据的节点，它的 **next 最终会指向合并后的链表头。

3.0148. 排序链表

3.1 题目大意

描述：给定链表的头节点 head。

要求：按照升序排列并返回排序后的链表。

说明：

  • 链表中节点的数目在范围 内。

示例：

img

1
2
 输入：head = [4,2,1,3]
 输出：[1,2,3,4]Copy to clipboardErrorCopied

img

1
2
 输入：head = [-1,5,3,4,0]
 输出：[-1,0,3,4,5]

解法：

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
 class Solution:
     def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
         # Base case
         if not head or not head.next:
             return head
 
         # Step 1: Split the list into two halves
         slow, fast = head, head.next
         while fast and fast.next:
             slow = slow.next
             fast = fast.next.next
 
         mid = slow.next
         slow.next = None  # Cut the list
 
         # Step 2: Sort each half recursively
         left = self.sortList(head)
         right = self.sortList(mid)
 
         # Step 3: Merge the sorted halves
         return self.merge(left, right)
 
     def merge(self, list1: ListNode, list2: ListNode) -> ListNode:
         dummy = ListNode(0)
         tail = dummy
 
         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
 
         # Connect remaining nodes
         tail.next = list1 if list1 else list2
         return dummy.next
 

这里其实用到了上一题的函数，也就是合并链表并排序。我们先将链表分成两半，然后递归地对每一半进行排序，最后再合并两个已排序的链表。