【ALBB面试题】
题目：
把两个有序的链表合并成一个有序的链表，例如 1 -> 5 -> 6 和 2 -> 3 -> 7 -> 8，合并之后变成了 1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 8。
解：
# 合并两个有序链表 class Node: def __init__(self, data): self.data = data self.next = None class Link: def __init__(self, head=None, tail=None): self.head = head self.tail = tail def append(self, x): node = Node(x) if self.head is None: self.head = node else: self.tail.next = node self.tail = node link_a = Link() link_b = Link() for i in range(1, 8): if i & 1: link_b.append(i) continue link_a.append(i) print("合并前：") print("link_a: ", end=" ") p = link_a.head while p: print(p.data, end="\t") p = p.next print() p = link_b.head print("link_b: ", end=" ") while p: print(p.data, end="\t") p = p.next def merge(link1, link2): # 合并函数 p1 = link1.head p2 = link2.head if not p1 or not p2: # 为空 return link1 if p1 else link2 while p1 and p2: # 不为空 minnode = p1 if p1.data <= p2.data else p2 if p1 is link1.head and p2 is link2.head: head = minnode tail = minnode else: tail.next = minnode tail = tail.next if p1.data < p2.data: p1 = p1.next else: p2 = p2.next if p1: tail.next = p1 else: tail.next = p2 newlink = Link() # 生成新的链表 newlink.head = head newlink.tail = tail return newlink a = merge(link_a, link_b) p = a.head print() print("合并后： ", end="") while p: print(p.data, end="\t") p = p.next