5

合并两（多）个排序的链表（算法17）

 2 years ago
source link: https://allenwind.github.io/blog/3009/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
Mr.Feng Blog

NLP、深度学习、机器学习、Python、Go

合并两（多）个排序的链表（算法17）

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

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

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

建立结点和链表

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

合并排序链表

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

不使用递归的方法如下

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

简单的测试

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()

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

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

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

推广：链表的排序


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK