如何合併兩個有序的單鏈表到一個有序列表

Question

我想合併兩個有序的單鏈表。我試圖找出問題所在，但我無法找到答案。輸出不是我所期待的。

第一列表

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 輸出給出

創建第二個鏈接列表

1-> 3-> 4-> 5-> 7-> 19->空

合併

19->空

Answer 1

的一個問題是在主方法

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

l1是列表19 - > NULL與同爲l2 19 - > NULL。所以合併似乎是正確的，問題是你用最後一個元素而不是第一個元素覆蓋了l1和l2。我希望這有幫助。

Answer 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; 

這是一個簡單的詳細解決方案。您可以通過創建一個將節點附加到新列表的方法來減少代碼量，但邏輯相同。