我在网上搜索了一种使用递归的链表的 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 。
谢谢
最佳答案
第一个错误如下:-
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 结尾的列表。并且在两个列表递归后重新连接它们以防止丢失原始列表
关于java - 使用 Java 对链表进行递归合并排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20026628/