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

Closed. This question needs to be more focused. It is not currently accepting answers. Learn more。
想改进这个问题吗？更新问题，使其只关注一个问题editing this post。
如何将已排序的链表（l2）作为一个整体插入另一个已排序的链表（l1）并维护这两个已排序的链表？
方法头应为：void insertList(LinkedList L2)
例如：

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

调用方法后，l1列表应为：

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

怎么能做到？

最佳答案

您正在寻找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()方法优化它以就地运行并修改其中一个列表，而不是创建新列表。算法非常相似，只是在插入有关调用extranext()的元素时需要格外小心。
我把修改算法的任务交给您，以便将list修改到位，因为一旦理解了上面的算法，就应该非常清楚如何进行修改。