题目一

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

• 大意：合并两个列表，返回一个新的列表，新的列表要把前边给定的两个列表链接起来。

思路：

其实就是把两个有序列表变成一个有序列表，只要维护两个指针，分别将当前最小的数复制到第三个列表中，然后将相应指针后移即可。道理很简单。

需要注意到是，python中，如果一个变量等于一个列表(比如，list1为一个列表，定义a1 = list1)，则这个变量(a1)其实类似c中的指针的概念(a1和list1等价，都是“指针”)，并不是拷贝了这个列表(如要实现拷贝复制，可以写a1 = list1[:])。
对于本题，这样的语法其实产生了两种写法，（见下边小节)。对于本题，两种写法都对，第一种写法比较简洁，但是却改变了原来的l1和l2列表，因为p3指针赋值的时候，直接用了l1或者l2的节点，那么下一次赋值的时候，便改变了这个节点的next指针。第二种写法采用了oj所定义的ListNode类的构造函数，直接用符合要求的l1或者l2的节点的val值创建一个新的node链接在l3后边，所以不改变原先的l1和l2列表。
所以，具体用哪一种，要根据知己需求定。

代码1(python)

# 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):
<!--more-->
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        p1 = l1
        p2 = l2
        l3 = ListNode(0)
        p3 = l3
        while l1 and l2:
            if l1.val < l2.val:
                p3.next = l1
                l1 = l1.next
            else:
                p3.next = l2
                l2 = l2.next
            p3 = p3.next
        p3.next = l1 if not l2 else l2
        return l3.next

代码2(python)

# 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
        """
        p1 = l1
        p2 = l2
        l3 = ListNode(0)
        p3 = l3
        while l1 and l2:
            if l1.val < l2.val:
                p3.next = ListNode(l1.val)
                p3 = p3.next
                l1 = l1.next
            else:
                p3.next = ListNode(l2.val)
                p3 = p3.next
                l2 = l2.next
        if not l1 and not l2:
            return l3.next
        elif not l1:
            while l2:
                p3.next = ListNode(l2.val)
                p3 = p3.next
                l2 = l2.next
            return l3.next
        else:
            while l1:
                p3.next = ListNode(l1.val)
                p3 = p3.next
                l1 = l1.next
            return l3.next

题目二

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

• 大意：明显是前一道题的升级版，这次是合并k个已排序列表到一个列表。

思路0：

其实，这个就是一个归并排序，和归并排序不同的是，归并排序开始我们需要假设所有顺序都是乱的，我们假定每一个数都是一个list，然后逐步减少list数目，加长每一个list长度，而这道题，相当于已经进行到一半的归并排序。
不过，这没有关系，因为归并是递归实现的，我们玩全可以按照归并的方法，做这道题，而且正好用到了上一个题的代码。

代码：（Python）

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

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if not lists:
            return None
        if len(lists) == 1:
            return lists[0]
        mid = len(lists) / 2
        left = self.mergeKLists(lists[:mid])
        right = self.mergeKLists(lists[mid:])
        return self.merge2Lists(left, right)

    def merge2Lists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        l3 = ListNode(0)
        p3 = l3
        while l1 and l2:
            if l1.val < l2.val:
                p3.next = l1
                l1 = l1.next
            else:
                p3.next = l2
                l2 = l2.next
            p3 = p3.next
        p3.next = l1 if not l2 else l2
        return l3.next

参考：
《百度百科 归并排序》( http://baike.baidu.com/link?url=V2OlIM61x3mTzbnICxp-CK5GD6CfSz1JHy4KWHLpcRbgd6LO8Nz9oYobdtF58Lat6-BfiB8F1NH2P49QW0vW9_ )

思路1：

用堆排序，用到了python的heapq这个数据结构。

代码(python):

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

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        ret, heap = [], []
        for li in lists:
            while li:
                heapq.heappush(heap, li.val)
                li = li.next
        while heap:
            ret.append(heapq.heappop(heap))
        return ret

思路2：

用python的排序，直接将所有列表的所有数放在一个列表中，然后直接用sorted()排序。
个人感觉：虽然投机取巧，但是速度一点也不慢，实际解决问题却最快速实用。

代码(Python):

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

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        ret = []
        for lst in lists:
            while lst:
                ret.append(lst.val)
                lst = lst.next
        return sorted(ret)