专访：合并两个排序单链表

本文介绍了专访：合并两个排序单链表的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

这是一个编程问题接受记者采访时笔试时提出。 你有两个已排序单链表，你必须把它们合并，并返回新列表的头部，而无需创建任何新的额外的节点。返回的列表应该进行排序，以及

该方法的签名是：     节点MergeLists（List1的节点，节点list2中）;

节点类如下：

类节点{     int数据;     下一节点; }

我尝试了许多解决方案，但没有创造额外的节点螺丝的东西。请大家帮帮忙。

下面是附带的博客文章techieme.in/merging-two-sorted-singly-linked-list/

解决方案

节点MergeLists（List1的节点，节点list2中）{   如果（List1的== NULL）返回list2中;   如果（list2中== NULL）返回List1中;   如果（list1.data＆LT; list2.data）{     list1.next = MergeLists（list1.next，list2中）;     返回List1中;   } 其他 {     list2.next = MergeLists（list2.next，List1中）;     返回list2中;   } }

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"

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

Node class is below:

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