Mergesort a LinkedList

Question

我尝试用Java在LinkedList上编写合并例程。如果有人能审查我的执行情况并指出问题，那就太好了。

public class LinkedListSort{
    static class Node<T extends Comparable<T>>{
        private T value;
        private Node<T> next;

        public Node(T value,Node<T> next){
            this.value = value;
            this.next = next;
        }

        public T getValue(){
          return this.value;    
        }

        public void setNext(Node<T> next){
          this.next = next;
        }

        public Node<T> getNext(){
         return this.next;
        }

        @Override
        public String toString(){
            if(this.next == null){
              return this.value.toString();
            }else{
              return this.value.toString() +"->"+next.toString();
            }
        }
    }
    private <T extends Comparable<T>> Node<T> getLastHalf(Node<T> list){
        if(list.getNext() == null) return list;
        //Get the last half of the list
        Node<T> current = list;
        Node<T> mid = list;
        int midCounter = 0;
        while(current != null){
            if(midCounter%2 == 0){
               mid = mid.getNext(); 
            }
            current = current.getNext();
            midCounter++;
        }
        return mid;
    }

    private <T extends Comparable<T>> Node<T> getFirstHalf(Node<T> list){
        if(list.getNext() == null) return list;
        Node<T> current = list;
        Node<T> mid = list;
        Node<T> accum = null;
        Node<T> accumPtr = accum;
        int midCounter = 0;
        while(current != null){
          if(midCounter%2 == 0){
           Node<T> fNode = new Node<T>(mid.getValue(),null);
           if(accum == null){
             accum = fNode;
             accumPtr = accum;  
           }else{
             accum.setNext(fNode);
             accum = accum.getNext();   
           }
           mid = mid.getNext();
          }
          current = current.getNext();
          midCounter++; 
        }
        return accumPtr;
    }   

    public <T extends Comparable<T>> Node<T> merge(Node<T> left,
                 Node<T> right){
        Node<T> merged = null;
        Node<T> head = merged;
        while((left != null) && (right != null)){
          Node<T> leftVal = new Node<T>(left.getValue(),null);
          Node<T> rightVal = new Node<T>(right.getValue(),null);
          if(leftVal.getValue().compareTo(rightVal.getValue())<0){
             if(head == null){
             head = leftVal;
             merged = head;      
             }
             else{
                head.setNext(leftVal);
                head = head.getNext();
             }
                 left = left.getNext();     
          }else{
             if(head == null){
                head = rightVal;
            merged = head;
             }
             else{
                head.setNext(rightVal);
            head = head.getNext();
             }
             right = right.getNext();             
          }
        }
        if((left  == null) && (right == null)){
           return merged;
        }
        else if(left == null){
                head.setNext(right);
            return merged;
        }
        else{
           head.setNext(left);
           return merged;       
        }
    }

    public <T extends Comparable<T>> Node<T> 
        sort(Node<T> list){
      assert(list != null);
      if(list.next == null){
         return list;   
      }
      else{
         //Get the first half of the list
         Node<T> firstHalf = getFirstHalf(list);
         //Get the other half of the list
         Node<T> lastHalf  = getLastHalf(list);
         //Sort the first half  
         Node<T> left = sort(firstHalf);
         //Sort the other half
         Node<T> right = sort(lastHalf);
         //Merge the sorted left half and right half
         Node<T> merged = merge(left,right);
         //Return the merged result
         return merged;         
      }         
    }

    public static void main(String[] args){
      Node<Integer> node0 = new Node<Integer>(1,null);
      Node<Integer> node1 = new Node<Integer>(5,node0);
      Node<Integer> node2 = new Node<Integer>(7,node1);
      Node<Integer> node3 = new Node<Integer>(3,node2);
      Node<Integer> node4  = new Node<Integer>(9,node3);

      Node<Integer> node5 = new Node<Integer>(1,null);

      Node<Integer> node6 = new Node<Integer>(2,null);
      Node<Integer> node7 = new Node<Integer>(7,node6);

      LinkedListSort sort1 = new LinkedListSort();
      Node<Integer> result = sort1.sort(node4);
      Node<Integer> result1 = sort1.sort(node5);
      Node<Integer> result2 = sort1.sort(node7);

      System.out.println(result);
      System.out.println(result1);
      System.out.println(result2);
    }
}

Answer 1

最初的几点评论：

• 你可以把你的列表一分为二，而不是把这两部分分开。下面是一个拆分方法的示例(我懒洋洋地使用javafx.util.Pair，但如果愿意，您可以创建自己的Pair-like类)。静态> Pair，Node>拆分( Node list) { if (list.getNext() == null)返回新Pair<>(list，null)；Node head = list.getNext()；Node current = head；//有效克隆Node head=新Node<>(list.getValue()，null)；Node currentHead =head；int midCounter = 0；而(current != null) { midCounter++；如果(midCounter %2 == 0) {currentHead.setNext(新的Node<>(tail.getValue()，null))；currentHead = currentHead.getNext()；尾巴= tail.getNext()；} current = current.getNext()；}返回新的Pair<>(头、尾)；}
• 因此，您需要稍微调整排序方法:公共静态> Node排序( Node list) { assert (list != null)；if (list.getNext() == null) {返回列表；}list.getNext{ Pair，Node>拆分=拆分(列表)；//排序前半部分Node left =排序(split.getKey())；//排序另一半Node向右=排序(split.getValue())；//合并排序的左半和右半返回合并(左，右)；}
• 您已经使用了静态方法已经足够的实例方法。我将向类添加一个私有构造函数(因为没有人需要构造它)，并将所有方法更改为静态方法。
• 小点:您可以将leftVal和rightVal的创建推迟到merge方法中的if语句中: if (left.getValue().compareTo(right.getValue()) < 0) { Node leftVal =新Node(left.getValue()，null)；if (head == null) { head = leftVal；merged = head；}left.getValue{ head.setNext(leftVal)；head = head.getNext()；} left = left.getNext()；} Node rightVal =新Node(right.getValue()，null)；if (head == null) { head = rightVal；merged = head；}right.getValue{ head.setNext(rightVal)；head = head.getNext()；} right = right.getNext()；}}