LeetCode鏈接

1.題目

將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節(jié)點組成的撮慨。

示例：
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

2.分析

這道題是很基本的鏈表題俭识。思路很簡單：

• 特殊值處理:L1和L2分別為空的時候
• 構(gòu)建一個新的鏈表（通過比較L1和L2的頭節(jié)點）冠场，確定頭節(jié)點res_head（一個小技巧：通過一個first_flag來控制僅僅只需要在循環(huán)第一次執(zhí)行的事情谱姓，這個就像開關(guān)躯畴，有無窮盡的組合）
• 不斷比較L1和L2上的節(jié)點茫藏，鏈接到新鏈表后面
• 當(dāng)L1或者L2其中一個節(jié)點提前用光误趴，那么把另一個后面那段鏈表直接接到新的鏈表上即可

3.解答

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        """
        思路：兩個鏈表都是有序的，那么分別遍歷兩個鏈表务傲，比較每一個節(jié)點凉当，匯集成一個新的鏈表
        """
        # ①特殊值處理
        if not l1:
            return l2

        if not l2:
            return l1

        # ②構(gòu)建新的有序鏈表（不斷比較l1和l2上的節(jié)點）
        current_1 = l1
        current_2 = l2
        first_flag = True  # 控制第一次才執(zhí)行事情的flag

        while current_1 and current_2:
            if first_flag:  # 構(gòu)建新的鏈表，確定新的頭結(jié)點res_head 
                res_head = current_1 if current_1.val < current_2.val else current_2
                first_flag = False
                if current_1.val < current_2.val:
                    current_1 = current_1.next
                else:
                    current_2 = current_2.next
                current = res_head
                continue
            if current_1.val < current_2.val:
                current.next = current_1  # 使得當(dāng)前節(jié)點指向新的節(jié)點
                current = current_1  # 構(gòu)建下一次循環(huán)使用的current 節(jié)點
                current_1 = current_1.next
            else:
                current.next = current_2
                current = current_2
                current_2 = current_2.next

        # ③處理剩余值
        current.next = current_1 if current_1 else current_2

        return res_head

簡潔點寫法：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: 'ListNode', l2: 'ListNode') -> 'ListNode':
        head = ListNode(0)
        node = head
        while l1 and l2:
            if l1.val <= l2.val:
                node.next = l1
                l1 = l1.next
            else:
                node.next = l2
                l2 = l2.next
            node = node.next
        if l1:
            node.next = l1
        if l2:
            node.next = l2
        return head.next