如何在保持排序的同时将排序的链表插入另一个排序的链表？

Question

如何将一个已排序的链表 (L2) 作为一个整体插入到另一个已排序的链表 (L1) 中并保持两者的排序？

方法头应该是：void insertList(LinkedList L2)

例如：

L1 = 1 → 2 → 3 → 10
L2 = 4 → 5 → 6

调用该方法后，L1 列表应为：

1 → 2 → 3 → 4 → 5 → 6 → 10

如何做到？

Answer 1

您正在寻找 merge sort 的合并阶段。

可以在 LinkedList 中简单地通过将两者迭代在一起来完成，并且每次将最小的元素推送到结果列表。

伪代码：

iter1 = list1.iterator()
iter2 = list2.iterator()
//before these commands make sure the lists are not empty:
curr1 = iter1.next(); 
curr2 = iter2.next();
List result = new LinkedList();
while curr1 != null && curr2 != null {
   if curr1 < curr2 { 
          result.add(curr1);
          curr1 = list1.next();
   } else { 
          result.add(curr2);
          curr2 = list2.next();
   }
}
while (curr1 != null) {
   result.add(curr1);
   curr1 = curr1.next();
}
while (curr2 != null) {
   result.add(curr2);
   curr2 = curr1.next();
}

小提示：在链表的情况下，您可以将其优化为运行就地并修改其中一个列表而不是创建新列表，如果需要，使用 ListIterator 接口和 add() 方法。该算法非常相似，只是在插入元素时需要格外小心以调用额外的 next().

我留给你修改算法来修改list，因为一旦理解了上面的算法，应该很清楚如何去做。

如何在保持排序的同时将排序的链表插入另一个排序的链表？

How can I insert a sorted linked list into another sorted one while maintaining it sorted?

java

arrays

sorting

algorithm

linked-list