问题：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。

原理：

不难想出一个递归思路。先比较两链表首结点大小。较小的结点称为新合拼链表的首结点，同时，该结点所在的链表指针向前移动一位，我们称该链表尾子链表。这样，下一步就是子链表和较大结点所在的链表的比较和操作。和第一个类似，以此递归下去，直到两链表指针指向None。

根据递归版本我们不难使用队列辅助空间实现，但使用递归更简洁，下面给出递归的实现过程。

实现：

建立结点和链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import random
from functools import total_ordering

@total_ordering
class Node:

    def __init__(self, value):
        self.value = value
        self.next = None

    def __repr__(self):
        return 'Node<{}>'.format(self.value)

    def __eq__(self, other):
        return self.value == other.value

    def __gt__(self, other):
        return self.value > other.value

def build_linked_list(values):
    if not values:
        return None
    root = Node(values[0])
    p_node = root
    for value in values[1:]:
        p_node.next = Node(value)
        p_node = p_node.next
    return root

合并排序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def travel_list(linked):
    while linked:
        yield linked
        linked = linked.next

def sorted_linked_list(p_head1, p_head2):
    if p_head1 is None:
        return p_head2
    if p_head2 is None:
        return p_head1

    p_node = None # 没有必要在这里创建，仅用于表示
    if p_head1 < p_head2:
        p_node = p_head1
        p_node.next = sorted_linked_list(p_head1.next, p_head2)
    else:
        p_node = p_head2
        p_node.next = sorted_linked_list(p_head1, p_head2.next)
    return p_node

不使用递归的方法如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def sorted_linked_list(p_head1, p_head2):
    if p_head1 is None:
        return p_head2
    if p_head2 is None:
        return p_head1

    p_node = None
    while p_head1 and p_head2:
        if p_head1 > p_head2:
            head = p_head2
            p_head2 = p_head2.next
        else:
            head = p_head1
            p_head1 = p_head1.next
        if p_node is None:
            p_node = head
        head = head.next
    if p_head1:
        head.next = p_head1
    else:
        head.next = p_head2
    return p_node

简单的测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def main():
    p_head1 = build_linked_list(sorted(random.sample(range(20), 5)))
    p_head2 = build_linked_list(sorted(random.sample(range(20), 5)))

    for node in travel_list(p_head1):
        print(node)

    for node in travel_list(p_head2):
        print(node)

    p_head = sorted_linked_list(p_head1, p_head2)
    for node in travel_list(p_head):
        print(node)

if __name__ == '__main__':
    main()

推广该问题，如果合并多个链表？

我们可以采取上述的思路，每个找出链表中最小的结点，作为头结点，然后该头结点所属的原先结点指针往后移动一个结点，以此下去。不使用递归的写法如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def find_min_node(lists):
    if not lists:
        return None
    _min = None
    index = 0
    for i, node in enumerate(lists):
        if _min is None:
            _min = node
        elif _min > node:
            _min = node
            index = i
    if _min.next:
        lists[index] = _min.next
    else:
        del lists[index]
    return _min

def merge_lists(lists):
    head = find_min_node(lists)
    p_node = head
    while lists:
        p_node.next = find_min_node(lists)
        p_node = p_node.next
    return head

推广：链表的排序

完。