java - 使用 Java 对链表进行递归合并排序

Question

我在网上搜索了一种使用递归的链表的 Java 合并排序算法的干净简单的实现。

我找不到一个不错的，所以我想在这里实现它。但我卡住了。

这是我目前所拥有的:

public List mergeSortList(Node head, Node tail) {

    if ((head == null) || (head.next == null))
        return;

    Node middle = this.findMiddle(head);
    List left = mergeSortList(this.head, middle);
    List right = mergeSortList(middle.next, tail);
    return merge(left, right);
}

private List merge(List left, List right) {
    List returnedList = new LinkedList();

}

private Node findMiddle(Node n) {
    Node slow, fast;
    slow = fast = n;

    while (fast != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

谁能帮我改正错误并填写 stub 。

谢谢

Answer 1

第一个错误如下:-

while(fast != null && fast.next.next != null)
{
   slow = slow.next;
   fast = fast.next.next;
}  

fast.next 在执行 fast.next.next 时可以为空，考虑到没有元素是奇数的情况。

这是修改后的代码:-

while(fast != null && fast.next.next != null)
{
    slow = slow.next;
    if(fast.next!=null)
        fast = fast.next.next;
    else break;
}  

这里是另一个修改:-

public List mergeSortList(Node head)
{
    if ( (head == null) || (head.next == null))
       return head;
    Node middle = this.findMiddle(head);
    Node first = head;
    Node second = middle.next;
    middle.next = null; 
    Node left = mergeSortList(first);
    Node right = mergeSortList(second);
    return merge(left, right);
 }

说明:您不需要将 tail 传递给函数，您可以将中间的列表拆分为两个单独的以 null 结尾的列表。并且在两个列表递归后重新连接它们以防止丢失原始列表