Merge Two sorted list 合并有序数列

Easy, Linked List

给定两个有序数列，合并成一个有序数列。

使用递归方法

1. 比较两个数列的第一个节点
2. 将第一个节点小的数列的剩余部分与另外一个数列继续比较
3. 重复步骤1，2

# 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
        """
        if l1 and l2:
            if l1.val < l2.val:
                l1.next = self.mergeTwoLists(l1.next,l2)
                return l1
            else:
                l2.next = self.mergeTwoLists(l1,l2.next)
                return l2
        else:
            return l1 or l2

更简洁的版本

# 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
        """
        if l1 and l2:
            #l1 always be the smaller head list
            if l2.val < l1.val:
                l1, l2 = l2, l1
                l1.next = self.mergeTwoLists(l1.next,l2)
        return l1 or l2

以上两个方法使用了迭代的思想，LeetCode处理linked list更常用的方法是指针。在新list前加入一个dummy head。然后使用一个指针来修改list。

# 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
        """
        dummyHead = ListNode(0)
        p = dummyHead
        while l1 != None and l2 != None:
            if l1.val < l2.val:
                p.next = l1
                l1 = l1.next
            else:
                p.next = l2
                l2 = l2.next
            p = p.next
        if l1!=None: p.next = l1
        if l2!=None: p.next = l2
        return dummyHead.next