LeetCode 筆記 - 21. Merge Two Sorted Lists

Posted on

題目在此 21. Merge Two Sorted Lists

給定兩個排序過的鏈結串列，請將它們合併成一個新的排序鏈結串列，並且回傳新的鏈結串列。

解題思維

這題的解法很直觀，因為兩個鏈結串列都是排序過的，所以我們可以使用雙指標法，一個指標 node1 用來遍歷 list1，另一個指標 node2 用來遍歷 list2。

藉由建立一個 dummy 節點來簡化邏輯，並且使用一個指標 cur_node 來記錄目前合併後的鏈結串列的最後一個節點。

剩下的就是比較 node1 和 node2 的值，將較小的節點接到 cur_node.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
# 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]:

        # step1: create a dummy head to store the first result node
        # step2: compare the current node of the two linked lists, and add the samller one to the end of dummy list
        # stpe3: return dummy list's next pointer
        # time complexity: O(m + n)
        # space complexity: O(1)

        dummy = ListNode()

        cur_node = dummy # the result linked list

        node1 = list1
        node2 = list2

        while node1 and node2:

            if node1.val < node2.val:
                cur_node.next = node1
                node1 = node1.next
            else:
                cur_node.next = node2
                node2 = node2.next

            cur_node = cur_node.next

        if node1:
            cur_node.next = node1
        if node2:
            cur_node.next = node2

        return dummy.next

也許你也會想看看