LeetCode解題之Merge Two Sorted Lists

原題

將兩個有序的鏈表拼接成一個有序的鏈表。

注意點：

例子：

輸入: l1 = 1->2->4, l2 = 3
輸出: 1->2->3->4

解題思路

為了避免分類討論，添加一個假的頭節點。現在只需要兩個指針分別指向原來的兩個鏈表，將其中比較小的節點添加到新的鏈表中。傳入的參數l1和l2正好可以當作遍歷兩個鏈表的指針。

AC源碼

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


class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        temp = ListNode(-1)
        head = temp
        while l1 and l2:
            if l1.val > l2.val:
                temp.next = l2
                l2 = l2.next
            else:
                temp.next = l1
                l1 = l1.next
            temp = temp.next
        if l1:
            temp.next = l1
        else:
            temp.next = l2
        return head.next


if __name__ == "__main__":
    assert Solution().mergeTwoLists(ListNode(1), ListNode(2)).val == 1

歡迎查看我的Github來獲得相關源碼。