以最有效的方式合并两个排序后的链表

最近我遇到了这个问题。我无法解决它，它是在啃我。我的代码不起作用，我不明白我哪里出错了。以最有效的方式合并两个排序后的链表

//Program to merge two sorted linked lists. 

public class LLMergeSort{ 
static Node head1; 
static Node head2; 
static Node newHead; 

static class Node{ 
    int data; 
    Node next; 

    Node(int d){data=d;next=null;} 
} 

public static void merge(Node head1,Node head2,Node newHead){ 

    Node curr1 = head1; 
    Node curr2 = head2; 

    while(curr1!=null && curr2!=null){ 
     if(curr1.data<curr2.data){ 
      Node new_node = new Node(curr1.data); 
      new_node.next = newHead; 
      newHead = new_node; 
      curr1 = curr1.next; 
     } 
     else{ 
      Node new_node = new Node(curr2.data); 
      new_node.next = newHead; 
      newHead = new_node; 
      curr2 = curr2.next; 
     } 
    } 

    if(curr1==null){ 
     while(curr2!=null){ 
      Node new_node = new Node(curr2.data); 
      new_node.next = newHead; 
      newHead = new_node; 
      curr2 = curr2.next; 
     } 
    } 
    else if(curr2==null){ 
     while(curr1!=null){ 
      Node new_node = new Node(curr1.data); 
      new_node.next = newHead; 
      newHead = new_node; 
      curr1 = curr1.next; 
     } 
    } 
    print(newHead); 
} 

private static void print(Node newHead){ 

    Node curr = newHead; 
    System.out.println("Linked list after merging both the lists : "); 
    while(curr!=null){ 
     System.out.print("["+curr.data+"]->"); 
     curr = curr.next; 
    } 
    System.out.print("NULL"); 
    System.out.println(); 
} 

public static void main(String[] args) { 

    LLMergeSort ll1 = new LLMergeSort(); 
    ll1.head1 = new Node(11); 
    ll1.head1.next = new Node(10); 
    ll1.head1.next.next = new Node(8); 
    ll1.head1.next.next.next = new Node(6); 

    LLMergeSort ll2 = new LLMergeSort(); 
    ll2.head2 = new Node(18); 
    ll2.head2.next = new Node(15); 
    ll2.head2.next.next = new Node(9); 
    ll2.head2.next.next.next = new Node(7); 
    ll2.head2.next.next.next.next = new Node(2); 

    LLMergeSort ll3 = new LLMergeSort(); 

    ll3.newHead = null; 

    merge(head1,head2,newHead); 

    } 
}

我是新来编码，所以如果有人觉得我的程序不符合标准，那么请告诉我。

来源

2017-01-07 Mayank Gupta

我不清楚你的代码是干什么的。也许描述你正试图解决的具体问题。但是，'next.next.next.next'肯定不符合标准。 –

在运行代码时，我得到了两个链接的列表，相互之间没有任何操作。我无法理解合并操作出错的位置。 –

欢迎来到堆栈溢出！看起来你正在寻求作业帮助。虽然我们本身没有任何问题，但请观察这些[应做和不应该]（http://meta.stackoverflow.com/questions/334822/how-do-i-ask-and-answer-homework-questions/338845＃338845），并相应地编辑您的问题。 –

不应该列出增加的价值而不是减少，如6,8,10,11，对比11,10,8,6？

因为合并是静态的，所以不需要有head1，head2和newHead作为成员的类。这些都可能是局部引用在主节点和合并（）可以返回一个参考节点，而不是采取第三个参数：

public static void main(String[] args) { 
    Node head1 = new Node(6); 
    head1.next = new Node(8); 
    // ... 
    Node head2 = new Node(2); 
    head2.next = new Node(7); 
    // ... 
    Node newHead = merge(head1, head2);

对于合并（），它的简单分配了一个“虚拟”节点，并有以“虚拟”节点的引用开始了工作参考节点：通过使用merged.next两个列表

Node dummy = new Node; // dummy.next will be the merged list 
    Node merged = dummy;  // working reference

然后合并和进步。完成后，返回dummy.next。您需要在开始时检查head1 == null或head2 == null。如果head1 == null使用head2，反之亦然。如果两者都为空则无关紧要。

来源

2017-01-07 21:47:30 rcgldr

谢谢！帮助我了解了我不断犯下的错误。 –

以最有效的方式合并两个排序后的链表

回答

相关问题