采访问题：合并两个排序的单链接列表，而不创建新节点 [英] Interview Question: Merge two sorted singly linked lists without creating new nodes

问题描述

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

This is a programming question asked during a written test for an interview. "You have two singly linked lists that are already sorted, you have to merge them and return a the head of the new list without creating any new extra nodes. The returned list should be sorted as well"

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

The method signature is: Node MergeLists(Node list1, Node list2);

Node类如下：

class Node{
    int data;
    Node next;
}

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

I tried many solutions but not creating an extra node screws things. Please help.

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

Here is the accompanying blog entry http://techieme.in/merging-two-sorted-singly-linked-list/

推荐答案

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

这篇关于采访问题：合并两个排序的单链接列表，而不创建新节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！