LeetCode链接

1.题目

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

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

2.分析

这道题是很基本的链表题。思路很简单：

• 特殊值处理:L1和L2分别为空的时候
• 构建一个新的链表（通过比较L1和L2的头节点），确定头节点res_head（一个小技巧：通过一个first_flag来控制仅仅只需要在循环第一次执行的事情，这个就像开关，有无穷尽的组合）
• 不断比较L1和L2上的节点，链接到新链表后面
• 当L1或者L2其中一个节点提前用光，那么把另一个后面那段链表直接接到新的链表上即可

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
        """
        """
        思路：两个链表都是有序的，那么分别遍历两个链表，比较每一个节点，汇集成一个新的链表
        """
        # ①特殊值处理
        if not l1:
            return l2

        if not l2:
            return l1

        # ②构建新的有序链表（不断比较l1和l2上的节点）
        current_1 = l1
        current_2 = l2
        first_flag = True  # 控制第一次才执行事情的flag

        while current_1 and current_2:
            if first_flag:  # 构建新的链表，确定新的头结点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  # 使得当前节点指向新的节点
                current = current_1  # 构建下一次循环使用的current 节点
                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