合并两个已排序的链表

Question

假设列表“A”是1-

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;

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

Answer 2

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

来自访谈：合并两个排序的单链表

我想你找不到比这个递归更清晰的算法了。

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