合并两个单独排序的链表，新列表排序规则不变☆☆☆

问题：

您有两个已经排序的单链接列表，您必须将它们合并并返回新列表的头，而无需创建任何新的额外节点。返回的列表也应排序。

方法签名为：

Node MergeLists(Node list1, Node list2);

节点类如下：

class Node{
   int data;
   Node next;
}

例：

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

解：

这是有关如何合并两个排序的链表A和B的算法：

while A not empty or B not empty:
   if first element of A < first element of B:
      remove first element from A
      insert element into C
   end if
   else:
      remove first element from B
      insert element into C
end while

这里C将是输出列表。

可能有两种解决方案：

递归方法是
1. 在传递的两个节点中，使该节点的值较小
2. 将较小的节点指向第二个链表中剩余的下一个较小的值
3. 返回当前节点（这是传递给该方法的两个节点中的较小者）
迭代方法对于所有实际目的都更好，因为列表的大小会随着规模的增加而扩大：
1. 将其中一个排序的链表视为列表，将另一个排序的链表视为“节点袋”。
2. 然后我们在列表中查找给定节点（从节点包中）的正确位置。

复杂度分析：

时间复杂度：O（n）

递归和迭代解决方案的运行时复杂度为或。O(n)

实现方式：

爪哇

递归解决方案：

Node MergeLists(Node list1, Node list2) {
  if (list1 == null) return list2;
  if (list2 == null) return list1;

  if (list1.data < list2.data) {
    list1.next = MergeLists(list1.next, list2);
    return list1;
  } else {
    list2.next = MergeLists(list2.next, list1);
    return list2;
  }
}

避免递归以避免分配新节点：

Node MergeLists(Node list1, Node list2) {
  if (list1 == null) return list2;
  if (list2 == null) return list1;

  Node head;
  if (list1.data < list2.data) {
    head = list1;
  } else {
    head = list2;
    list2 = list1;
    list1 = head;
  }
  while(list1.next != null) {
    if (list1.next.data > list2.data) {
      Node tmp = list1.next;
      list1.next = list2;
      list2 = tmp;
    }
    list1 = list1.next;
  } 
  list1.next = list2;
  return head;
}

Y

递归：

def merge_lists(h1, h2):
    if h1 is None:
        return h2
    if h2 is None:
        return h1

    if (h1.value < h2.value):
        h1.next = merge_lists(h1.next, h2)
        return h1
    else:
        h2.next = merge_lists(h2.next, h1)
        return h2

迭代式：

def merge_lists(head1, head2):
    if head1 is None:
        return head2
    if head2 is None:
        return head1

    # create dummy node to avoid additional checks in loop
    s = t = node() 
    while not (head1 is None or head2 is None):
        if head1.value < head2.value:
            # remember current low-node
            c = head1
            # follow ->next
            head1 = head1.next
        else:
            # remember current low-node
            c = head2
            # follow ->next
            head2 = head2.next

        # only mutate the node AFTER we have followed ->next
        t.next = c          
        # and make sure we also advance the temp
        t = t.next

    t.next = head1 or head2

    # return tail of dummy node
    return s.next

常见问题FAQ