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

Question

<分区>

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接口(interface)和 add() 方法。该算法非常相似，只是在插入元素时需要格外小心以调用额外的 next()。

我留给您修改算法以就地修改 list，因为一旦理解了上述算法，应该非常清楚如何去做。