如何使用链表中的Java归并我实现？

Question

我如何能实现“归并”使用链表在Java中使用下面的执行？ 这是我实现链表：

public class LinkedList { 
    Node tail; 

    public LinkedList() { 
     tail = null; 
    } 

    public LinkedList(Object value) { 
     tail = new Node(value); 
     tail.setNext(tail); 
    } 

    public void purge() { 
     tail = null; 
    } 

    public Object getFirst() { 
     Node rigby = tail.getNext(); 
     return rigby.getValue(); 
    } 

    public Object getLast() { 
     return tail.getValue(); 
    } 

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

    public void assign(LinkedList list) { 
     if (list.isEmpty()) 
      tail = null; 
     else { 
      this.append(list.tail.getNext().getValue()); 

      Node tmp = list.tail.getNext(); 
      while (tmp != list.tail) { 
       tmp = tmp.getNext(); 
       this.append(tmp.getValue()); 
      } 
     } 
    } 

    public void append(Object value) { 
     if (this.isEmpty()) { 
      tail = new Node(value); 
      tail.setNext(tail); 
     } else { 
      Node tmp = new Node(value); 
      tmp.setNext(tail.getNext()); 
      tail.setNext(tmp); 
      tail = tmp; 
     } 
    } 

    public void prepend(Object value) { 
     if (this.isEmpty()) { 
      tail = new Node(value); 
      tail.setNext(tail); 
     } else { 
      Node tmp = new Node(value); 
      tmp.setNext(tail.getNext()); 
      tail.setNext(tmp); 
     } 
    } 

    public boolean equals(LinkedList list) { 
     if (this != list) { 
      // temp variables 
      Node mordecai = tail.getNext(); 
      Node rigby = list.tail.getNext(); 
      // previouses 
      Node prev = tail; 
      Node prev2 = list.tail; 
      while (true) { 
       if (mordecai.getValue().getClass().getName() == "Node") { 
        if (!mordecai.getValue().equals(rigby.getValue())) 
         return false; 
       } else { 
        if (!mordecai.getValue().toString().equals(rigby.getValue().toString())) 
         return false; 
       } 
       prev = mordecai; 
       mordecai = mordecai.getNext(); 
       prev2 = rigby; 
       rigby = rigby.getNext(); 

       if ((prev == tail) && (prev2 == list.tail)) 
        return true; 
       if ((prev == tail) || (prev2 == list.tail)) 
        return false; 
      } 

     } 
     return true; 
    } 


    public void extract(Object value) { 
     if (!this.isEmpty()) { 
      Node tmp = tail.getNext(); 
      Node prev = tail; 
      while (true) { 
       if (tmp.getValue().equals(value)) { 
        prev.setNext(tmp.getNext()); 
        break; 
       } 
       prev = tmp; 
       tmp = tmp.getNext(); 

       if (prev == tail) 
        break; 
      } 
     } 
    } 

    public String toString() { 
     if (this.isEmpty()) { 
      return null; 
     } else { 
      String str = ""; 
      Node tmp = tail.getNext(); 
      str += tmp.getValue().toString(); 
      while (tmp != tail) { 
       str += " -> "; 
       tmp = tmp.getNext(); 
       str += tmp.getValue().toString(); 
      } 
      return str; 
     } 
    } 


    class Node { 
     Object data; 
     Node next; 

     public Node(Object value) { 
      data = value; 
     } 

     public Node(Object value, Node pointer) { 
      data = value; 
      next = pointer; 
     } 

     public Object getValue() { 
      return data; 
     } 

     public void setValue(Object value) { 
      data = value; 
     } 

     public Node getNext() { 
      return next; 
     } 

     public void setNext(Node pointer) { 
      next = pointer; 
     } 

     public boolean equals(Node var) { 
      if (next.equals(var.next)) { 
       if (data.getClass().getName() == "Node") { 
        if (data.equals(var.data)) 
         return true; 
       } else { 
        if (data.toString().equals(var.data.toString())) 
         return false; 
       } 

      } 
      return false; 
     } 
    } 
} 

我不能作出正面或反面和分析给了我的偏头痛。我需要帮助。我搜索了，我只找到一个数组实现。

Answer 1

Collections.sort()是在Java merge sort

public static <T> void sort(List<T> list, 
         Comparator<? super T> c) 

Java文档

是修饰的归并（其中合并是如果在低子列表中的最高元素小于省略排序算法高级子列表中最低的元素）。该算法提供了有保证的n log（n）性能。指定的列表必须是可修改的，但不需要调整大小。此实现将指定列表转储到一个数组，排序的阵列，且迭代列表复位来自阵列中的对应位置的每个元素。这样就避免了会导致试图排序代替链表N2的log（n）性能。

Answer 2

如果从解决方案的抽象描述工作你会在你以后的课业做的更好;）http://en.wikipedia.org/wiki/Merge_sort