最も効率的な方法でソートされた2つのリンクリストをマージする

Question

最近、私はこの問題に遭遇しました。私はそれを解決することができず、それは私を悩ましています。私のコードは機能しません。

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

    } 
} 

誰かが私のプログラムが標準に達していないと感じたら、私はコーディングに新しいです。

Answer 1

リストが減少するのではなく値が増えないようにする必要があります（たとえば、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を使用して2つのリストを通じ

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を使用するか、またはその逆の場合両方がnullの場合は問題ありません。