在链接列表上合并排序

Question

所以我一直在尝试使用合并排序来对链表进行排序，我发现这个代码并试图在它上面工作，但它并没有真正起作用？

有什么问题呢？我不太清楚getMiddle方法，尽管我知道它应该得到列表的中间值，以便从列表本身处理2个列表

下面是代码;

public Node mergeSort(Node head) { 

    if (head == null || head.link == null) { 
     return head;  
    } 

    Node middle = getMiddle(head); 

    Node sHalf = middle.link; 
    middle.link = null;  

    return merge(mergeSort(head), mergeSort(sHalf)); 
} 

public Node merge(Node a, Node b) { 
    Node dummyHead; 
    Node current; 

    dummyHead = new Node(); 
    current = dummyHead; 

    while (a != null && b != null) { 
     if ((int) a.getData() <= (int) b.getData()) { 
      current.link = a; 
      a.link = a; 
     } 
     else { 
      current.link = b; 
      b.link = a; 
     } 
     current = current.link; 
    } 
    current.link = (a == null) ? b : a; 
    return dummyHead; 
} 

public Node getMiddle(Node head) { 
    if (head == null) { 
     return head; 
    } 
    Node slow, fast; 
    slow = fast = head; 
    while (fast.link != null && fast.link.link != null) { 
     slow = slow.link; 
     fast = fast.link.link; 
    } 
    return slow; 
} 

在main方法：

Object data; 
    MyLinkedList list = new MyLinkedList();   //empty list. 


    for (int i = 0; i < 3; i++) {   //filling the list 
     data = console.nextInt(); 
     list.insertAtFront(data); 
    } 


    System.out.print("Print(1): "); 
    list.printList(); 

    list.mergeSort(list.getHead()); 
    System.out.print("List after sorting: "); 
    list.printList(); 

Answer 1

的一个问题是getMiddle方法不正确返回中间Node。

考虑具有5个节点（A，B，C，d，E）的链接列表

head，slow，和fast都开始在索引0（a）中。

的while循环的第一次迭代之后，slow为1（b）和fast是在图2（c）;在第二次迭代之后，slow处于2（c）并且在4（e）处快。这些都不是空的，所以又发生了一次迭代，在3（d）处放慢，在null处放慢。由于fast为空，退出while循环并返回slow;然而slow具有节点3（d）而不是中间节点2（c）。

的另一种方法来获取中间节点是简单地使用节点的数量：

public Node getMiddle(Node head) { 
    Node counter = head; 
    int numNodes = 0; 
    while(counter != null) { 
     counter = counter.link; 
     numNodes++; 
    } 
    if(numNodes == 0) 
     return null; 
    Node middle = head; 
    for(int i=0; i<numNodes/2; i++) 
     middle = middle.link; 
    return middle; 
} 

我你mergeSort方法是好的，但在技术上只需要返回head如果head.link是null，不如果head本身null（因为这永远不会发生，无论如何）：

public Node mergeSort(Node head) { 
    if (head.link == null) { 
     return head;  
    } 
    // same 
} 

最重要的是，你的merge方法。你可以在你的Node类中写一个public void setData(Object)方法来使这更容易。下面的代码应该工作，虽然我不能要求它做的工作

public Node merge(Node a, Node b) { 
    Node combined = new Node(); 
    Node current = combined; 
    while(a != null || b != null) { 
     if(a == null) 
      addNode(current, b); 
     if(b == null) 
      addNode(current, a); 
     if((int)a.getData()<(int)b.getData()) 
      addNode(current, a); 
     else 
      addNode(current, b); 
    } 
    return combined; 
} 

最好/最有效的方式使用下列helper方法：

public void addNode(Node n1, Node n2) { 
    n1.setData((int)n2.getData()); 
    n1.link = new Node(); 
    n1 = n1.link; 
    n2 = n2.link 
}