采访问题：合并两个排序的单链接列表，而不创建新节点

小编典典

采访问题：合并两个排序的单链接列表，而不创建新节点

algorithm

这是在笔试中进行面试时要提出的编程问题。“您有两个已经排序的单链接列表，您必须合并它们并返回新列表的头，而无需创建任何新的额外节点。返回的列表也应排序”

方法签名为：Node MergeLists（Node list1，Node list2）；

节点类如下：

class Node{
    int data;
    Node next;
}

我尝试了许多解决方案，但没有创建额外的节点来解决问题。请帮忙。

这是随附的博客条目 http://techieme.in/merging-two-sorted-singly-linked-
list/

阅读 232

2020-07-28

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

2020-07-28