algorithm - 合并两个排序的链表

Question

假设列表“A”是 1->3->5，列表“B”是 4->6->7 如果合并后需要对它们进行排序，您将如何处理它们的合并 我想分享我对此的看法，如果需要改进，请告诉我，

i) Compare first node of 'B' with each node of 'A'
while A.val<B.val
A=A.next
We get 'A' pointing to node whose value is lesser than node of 'B'
ii) As per the example, intent is to store '4' in '3' 's reference and prior to that store '3' 's reference in a temp

iii) The same will have to be done for nodes in 'A', as in '5' will have to be stored between 4 and 6

请审阅此内容并帮助我即兴创作

Answer 1

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;
  }
}

来自 Interview: Merging two Sorted Singly Linked List

我认为您不会找到比这个递归更清晰的算法。

如果您想采用迭代方式，您也可以在我链接给您的帖子中找到另一个答案。