以最有效的方式合併兩個排序後的鏈表

最近我遇到了這個問題。我無法解決它，它是在啃我。我的代碼不起作用，我不明白我哪裏出錯了。以最有效的方式合併兩個排序後的鏈表

//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

謝謝！幫助我瞭解了我不斷犯下的錯誤。 –

以最有效的方式合併兩個排序後的鏈表

回答

相關問題