问题描述
这是在笔试中进行面试时提出的编程问题。
您有两个已经排序的单链接列表,您必须将它们合并并返回新列表的头,而无需创建任何新的额外节点。返回的列表也应进行排序
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.
以下是随附的博客条目
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;
}
}
这篇关于采访问题:合并两个排序的单链接列表,而不创建新节点的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!