使用第三個參考的兩個鏈接列表的遞歸合併排序

Question

我想解決使用第三個參考的遞歸合併排序。我希望獲取第三個引用，並繼續按排序順序鏈接兩個鏈接列表中的節點（兩個鏈接列表單獨排序），而不創建任何額外的節點。我發現有一個遞歸程序here。但我想用第三個參考來嘗試這個，但我一直在搞這個。任何人都可以讓我知道我在這裏錯過了什麼條件？

import java.util.ArrayList; 
import java.util.ListIterator; 

public class MergeLinkedListsIntoExisting { 
    public static void main(String[] args){ 
     Node nodeList1 = null, nodeList2 = null; 
     Node temp = null; 
     ArrayList<Integer> array1 = new ArrayList<Integer>(); 
     array1.add(3); 
     array1.add(7); 
     array1.add(9); 

     ArrayList<Integer> array2 = new ArrayList<Integer>(); 
     array2.add(1); 
     array2.add(2); 
     array2.add(8); 

     nodeList1 = add(nodeList1, array1); 
     nodeList2 = add(nodeList2, array2); 
     System.out.println("**List 1**"); 
     print(nodeList1); 
     System.out.println("**List 2**"); 
     print(nodeList2); 
     System.out.println("Sorted List"); 
     Node nodeList3 = mergeTwoLists(nodeList1, nodeList2, temp); 
     print(nodeList3); 
    } 
    private static Node add(Node node, ArrayList<Integer> list){ 
     Node current = node; 
     Node head = node; 
     ListIterator<Integer> it = list.listIterator(); 
     while(it.hasNext()){ 
      if(head==null){ 
       head = new Node(); 
       head.data = it.next(); 
       head.next=null; 
       node = head; 
      } 
      else{ 
       current = new Node(); 
       current.data = it.next(); 
       current.next = null; 
       node.next = current; 
       node = node.next; 
      } 
     } 
     return head; 
    } 

    private static void print(Node node) { 
     if(node!=null){ 
      while(node.next!=null){ 
       System.out.print(node.data + " "); 
       node = node.next; 
      } 
      System.out.println(node.data); 
     } 
     else{ 
      System.out.println("No elements in the linkedList."); 
     } 
    } 


    private static Node mergeTwoLists(Node nodeList1, Node nodeList2, Node temp) { 
     if(nodeList1 == null) return nodeList2; 
     if(nodeList2 == null) return nodeList1; 

     if(nodeList1.data <= nodeList2.data){ 
      if(temp == null){ 
       temp = nodeList1; 
       temp.next = mergeTwoLists(nodeList1.next, nodeList2, temp.next); 
      } 
      else{ 
       System.out.println(temp.data); 
       temp.next = mergeTwoLists(nodeList1.next, nodeList2, temp.next); 
      } 
     }else{ 
      if(temp == null){ 
       temp = nodeList2; 
       System.out.println(temp.data); 
       temp.next = mergeTwoLists(nodeList1, nodeList2.next, temp.next); 
      } 
      else{ 
       System.out.println(temp.data); 
       temp.next = mergeTwoLists(nodeList1, nodeList2.next, temp.next); 
      } 
     } 
     return temp; 
    } 
} 

該解決方案應該與temp.next在遞歸調用mergeTwoLists。根據需要糾正我和我的方法。

Answer 1

編輯：我只是看着這再次，我認爲固定的代碼只是去掉特殊情況下爲臨時的主要修改等於空。

我剛剛修改你的代碼，並得到它的工作。只需通過temp而不是temp.next，如果temp爲空，則不需要特殊情況。

import java.util.ArrayList; 
import java.util.ListIterator; 

public class MergeLinkedListsIntoExisting { 
    public static void main(String[] args){ 
     Node nodeList1 = null, nodeList2 = null; 
     Node temp = null; 
     ArrayList<Integer> array1 = new ArrayList<Integer>(); 
     array1.add(3); 
     array1.add(7); 
     array1.add(9); 

     ArrayList<Integer> array2 = new ArrayList<Integer>(); 
     array2.add(1); 
     array2.add(2); 
     array2.add(8); 

     nodeList1 = add(nodeList1, array1); 
     nodeList2 = add(nodeList2, array2); 
     System.out.println("**List 1**"); 
     print(nodeList1); 
     System.out.println("**List 2**"); 
     print(nodeList2); 
     System.out.println("Sorted List"); 
     Node nodeList3 = mergeTwoLists(nodeList1, nodeList2, temp); 
     print(nodeList3); 
    } 
    private static Node add(Node node, ArrayList<Integer> list){ 
     Node current = node; 
     Node head = node; 
     ListIterator<Integer> it = list.listIterator(); 
     while(it.hasNext()){ 
      if(head==null){ 
       head = new Node(); 
       head.data = it.next(); 
       head.next=null; 
       node = head; 
      } 
      else{ 
       current = new Node(); 
       current.data = it.next(); 
       current.next = null; 
       node.next = current; 
       node = node.next; 
      } 
     } 
     return head; 
    } 

    private static void print(Node node) { 
     if(node!=null){ 
      while(node.next!=null){ 
       System.out.print(node.data + " "); 
       node = node.next; 
      } 
      System.out.println(node.data); 
     } 
     else{ 
      System.out.println("No elements in the linkedList."); 
     } 
    } 


    private static Node mergeTwoLists(Node nodeList1, Node nodeList2, Node temp) { 
     if(nodeList1 == null) return nodeList2; 
     if(nodeList2 == null) return nodeList1; 

     if(nodeList1.data <= nodeList2.data){ 

      temp = nodeList1; 
      temp.next = mergeTwoLists(nodeList1.next, nodeList2, temp); 

     }else{ 

      temp = nodeList2; 
      temp.next = mergeTwoLists(nodeList1, nodeList2.next, temp);     
     } 
     return temp; 
    } 
} 

public class Node{ 
    int data; 
    Node next; 
} 

Answer 2

如果你想遞歸方法<那就試試這個

private static Node mergeTwoLists(Node nodeList1, Node nodeList2) { 
    if(nodeList1 == null) return nodeList2; 
    if(nodeList2 == null) return nodeList1; 
    Node tmp = new Node(); 
    if(nodeList1.data <= nodeList2.data){ 
     tmp.data = nodeList1.data; 
     tmp.next = mergeTwoLists(nodeList1.next, nodeList2); 
    }else{ 
     tmp.data = nodeList2.data; 
     tmp.next = mergeTwoLists(nodeList1, nodeList2.next); 
    } 
    return temp; 
}