以Java的方式合併排列LinkedList

Question

所以，任務是實現鏈接列表和合並排序鏈接列表。我完全意識到，在行業中，我很可能不必實現其中的任何一種，但我認爲這是練習Java的好方法。以下是我已經得到了這一點：

Node類：

public class Node<E extends Comparable<E>> 
    { 

    public E data; 
    public Node<E> next; 

    public Node(E data) 
    { 
     this.data = data; 
     next = null; 
    } 

    public void printData() 
    { 
     System.out.print(data + " "); 
    } 
} 

LinkedList類：

public class LinkedList<E extends Comparable<E>> 
{ 

    protected Node<E> root; 
    protected int size = 0; 

    public LinkedList() 
    { 
     root = null; 
    } 


    public void addBeg(E e) 
    { 

     Node<E> newNode = new Node<E>(e); 
     newNode.next = root; 
     root = newNode; 

     size++; 
    } 

    public Node deleteBeg() 
    { 
     Node<E> temp = root; 
     if(!isEmpty()) 
     { 
      root = root.next; 
      size--; 
     } 
     return temp; 
    } 

    public void setRoot(Node<E> newRoot) 
    { 
     root = newRoot; 
    } 

    public boolean isEmpty() 
    { 
     return root == null; 
    } 

    public Node<E> getRoot() 
    { 
     return root; 
    } 

    public void printList() 
    { 
     Node<E> cur = root; 
     while(cur!=null) 
      { 
       cur.printData(); 
       cur=cur.next; 
      } 
     System.out.println();   
    } 
} 

MergeSorter類：

public class MergeSorter<E extends Comparable<E>> 
{ 

    public MergeSorter() 
    { 

    } 

    private void split(LinkedList<E> list, LinkedList<E> firHalf, LinkedList<E> secHalf) 
    { 
     //if 0 or only 1 elements in the list - it doesn't seem to work, however 
     if(list.getRoot() == null || list.getRoot().next == null)firHalf = list; 
     else{ 
      Node<E> slow = list.getRoot(); 
      Node<E> fast = list.getRoot().next; 
      while(fast!=null) 
      { 
       fast = fast.next; 
       if(fast!=null) 
       { 
        fast = fast.next; 
        slow = slow.next; 
       } 
      } 
      //If I use the following line firHalf list is empty when in the caller of this method (it's not in this method, however). Don't understand why): 
      //firHalf = list; 
      firHalf.setRoot(list.getRoot()); 
      secHalf.setRoot(slow.next); 
      slow.next = null; 
     } 

    } 



    private LinkedList<E> merge(LinkedList<E> a, LinkedList<E> b) 
    { 
     LinkedList<E> mergedList = new LinkedList<E>();  
     Node<E> dummy = new Node<E>(null); 
     Node<E> tail = dummy; 

     while(true) 
     {   
      if(a.getRoot() == null){ 
       tail.next = b.getRoot(); 
       break; 
      } 
      else if(b.getRoot() == null){ 
       tail.next = a.getRoot(); 
       break; 
      } 

      else 
      { 
       if(a.getRoot().data.compareTo(b.getRoot().data) <= 0) 
       { 
        tail.next = a.getRoot(); 
        tail = tail.next; 
        a.setRoot(a.getRoot().next); 
       } 

       else 
       { 
        tail.next = b.getRoot(); 
        tail = tail.next; 
        b.setRoot(b.getRoot().next); 
       } 
       tail.next = null; 
      } 

     } 
     mergedList.setRoot(dummy.next); 
     return mergedList; 
    } 

    public void mergeSort(LinkedList<E> list) 
    { 
     Node<E> root = list.getRoot(); 
     LinkedList<E> left = new LinkedList<E>(); 
     LinkedList<E> right = new LinkedList<E>(); 

     if(root == null || root.next == null) return; //base case 
     split(list, left, right); //split 

     mergeSort(left); 
     mergeSort(right); 

     list = merge(left, right); // when this mergeSort returns this list should be 
            // referenced by the left or right variable of the 
            // current mergeSort call (but it isn't!) 
    } 
} 

我對Java相當陌生（來自C背景），所以如果我的代碼完全錯誤，我真的很抱歉。當我獨立地測試MergeSorter類中的拆分和合並方法時，一切似乎都奏效（拆分由0或1個元素組成的列表不起作用，並且使我瘋狂，但這不是合併排序所需的）。然而，mergeSort方法不起作用，我似乎無法找到方法。我試圖自己調試它，當兩個半部分合併到一個列表中，然後遞歸返回時，似乎會出現問題。新的合併列表應該被當前mergeSort調用的左或右變量引用，但是我只能得到最後一個元素而不是整個列表。

Answer 1

Java中的方法參數總是按值傳遞。

這可能有點混亂，因爲對象總是通過引用來訪問，所以你可能認爲它們是通過引用傳遞的;但他們不是。而是，引用是按值傳遞的。

這意味着，一個方法是這樣的：

public void methodThatDoesNothing(Object dst, Object src) { 
    src = dst; 
} 

實際上什麼也不做。它修改其局部變量src以引用與局部變量dst相同的對象，但這些只是當函數返回時消失的局部變量。它們與變量或表達式傳遞到方法中完全分開。

所以，在你的代碼，這樣的：

firHalf = list; 

並沒有真正做任何事情。我猜你想要的是：

while (! firHalf.isEmpty()) { 
    firHalf.deleteBeg(); 
} 
if (! list.isEmpty()) { 
    firHalf.addBeg(list.root().data); 
} 

其修改由firHalf的反對簡稱所以它具有相同的零或一元素list。