专访：合并两个排序单链表 [英] Interview: Merging two Sorted Singly Linked List

问题描述

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

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

节点类如下：

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

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

下面是附带的博客文章<一个href="http://techieme.in/merging-two-sorted-singly-linked-list/">http://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 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屋！