2つの順序付き単一リンクリストを1つの順序リストにマージする方法

Question

2つの順序付きリストをマージしようとしています。私はどこに問題があるのか​​調べてみましたが、答えを見つけることができません。出力は私が期待しているものではありません。

最初のリスト

の11-> 12-> 13-> 15-> 17-> 19インチ>ヌル

： 出力は

class Test 
{ 
Node head; // head of list 
class Node 
{ 
    int data; 
    Node next; 
    Node(int d){ 
     data = d; 
     next = null; 
    } 
} 

void sortedInsert(Node newNode) 
{ 
    Node current; 
    if (head == null || head.data >= newNode.data) 
    { 
     newNode.next = head; 
     head = newNode; 
    } 
    else { 
     current = head; 
     while (current.next != null && current.next.data < newNode.data) 
      current = current.next; 

     newNode.next = current.next; 
     current.next = newNode; 
    } 
} 
Node newNode(int data) 
{ 
    Node x = new Node(data); 
    return x; 
} 

/* Function to print linked list */ 
void printList() 
{ 
    Node temp = head; 
    while (temp != null) 
    { 
     System.out.print(temp.data+"-> "); 
     temp = temp.next; 
    } 
    System.out.print("null\n"); 
} 

Node mergeLists(Node list1, Node list2) { 
    Node result; 
    if (list1 == null) return list2; 
    if (list2 == null) return list1; 
    if (list1.data < list2.data) { 
     result = list1; 
     result.next = mergeLists(list1.next, list2); 
    } else { 
     result = list2; 
     result.next = mergeLists(list2.next, list1); 
    } 
    return result; 
} 

/* Drier function to test above methods */ 
public static void main(String args[]) 
{ 
    Test oneList = new Test(); 
    Test twoList = new Test(); 
    Test joinList = new Test(); 
    Node l1,l2,join; 

    //First linked list 
    l1 = oneList.newNode(11); 
    oneList.sortedInsert(l1); 
    l1 = oneList.newNode(13); 
    oneList.sortedInsert(l1); 
    l1 = oneList.newNode(12); 
    oneList.sortedInsert(l1); 
    l1 = oneList.newNode(17); 
    oneList.sortedInsert(l1); 
    l1 = oneList.newNode(15); 
    oneList.sortedInsert(l1); 
    l1 = oneList.newNode(19); 
    oneList.sortedInsert(l1); 
    System.out.println("First List"); 
    oneList.printList(); 

    //Second Linked List 
    l2 = twoList.newNode(1); 
    twoList.sortedInsert(l2); 
    l2 = twoList.newNode(5); 
    twoList.sortedInsert(l2); 
    l2 = twoList.newNode(3); 
    twoList.sortedInsert(l2); 
    l2 = twoList.newNode(7); 
    twoList.sortedInsert(l2); 
    l2 = twoList.newNode(4); 
    twoList.sortedInsert(l2); 
    l2 = twoList.newNode(19); 
    twoList.sortedInsert(l2); 
    System.out.println("Created Second Linked List"); 
    twoList.printList(); 

    join=joinList.mergeLists(l1,l2); 
    System.out.println("Merge"); 
    joinList.sortedInsert(join); 
    joinList.printList(); 
} 
} 

OUTPUT以下に示します。

第2のリンクリストを作成

1-> 3-> 4-> 5-> 7> 19->ヌル

マージ

19->ヌル

Answer 1

一つの問題は、主です> NULLとl2 19に同じ - - > NULL方法

oneList.sortedInsert(l1); 
l1 = oneList.newNode(15); 
oneList.sortedInsert(l1); 
l1 = oneList.newNode(19); 

l1は、リスト19です。したがって、マージが正しいように見えますが、問題は、l1とl2を最初の要素ではなく最後の要素で上書きしていることです。私はこれが役立つことを願っています

Answer 2

リストが適度に大きければスタックをオーバーフローさせるので、これは再帰的に行いたくありません。 2つのリストをマージするのは単純な反復操作です。基本的な考え方は次のとおりです。

if (list1 == null) return list2; 
if (list2 == null) return list1; 

Node head = null; 
Node l1 = list1; 
Node l2 = list2; 

if (l1.data < l2.data) 
{ 
    head = l1; 
    l1 = l1.next; 
} 
else 
{ 
    head = l2; 
    l2 = l2.next; 
} 

Node current = head; 
// while not at end of either list 
while (l1 != null && l2 != null) 
{ 
    if (l1.data < l2.data) 
    { 
     current.next = l1; 
     l1 = l1.next; 
    } 
    else 
    { 
     current.next = l2; 
     l2 = l2.next; 
    } 
    current = current.next; 
    current.next = null; 
} 
// at this point, you are at the end of one or both of the lists 
// Pick up the potential remainder from the list that's not at the end. 
// Note that only one of these loops will be entered. 
while (l1 != null) 
{ 
    current.next = l1; 
    current = current.next; 
    current.next = null; 
    l1 = l1.next; 
} 
while (l2 != null) 
{ 
    current.next = l2; 
    current = current.next; 
    current.next = null; 
    l2 = l2.next; 
} 
return head; 

これは単純な冗長な解決策です。新しいリストにノードを追加するメソッドを作成することで、コードの量を少し減らすことができますが、ロジックは同じです。