目前我正在学习使用链表进行合并排序。我不太明白如何将原来的ListNode一分为二。
我不太明白为什么ListNode left = mergeSort(head);不是整个原ListNode的头而不是左半部分？为什么方法getMiddleNode只返回slowttr？
正如我所假设的，ListNode left = mergeSort(head);只包含左半部分，但我想了解头部是如何变成半部分的。
谢谢！
这是我的代码
class Solution {
public ListNode mergeSort(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode middle = getMiddleNode(head);
ListNode left = mergeSort(head);
ListNode right = mergeSort(middle);
return merge(left, right);
}
ListNode getMiddleNode(ListNode head)
{
ListNode pre = null;
ListNode slowptr = head;
ListNode fastptr = head;
while(fastptr != null || fastptr.next != null)
{
pre = slowptr;
slowptr = slowptr.next;
fastptr = fastptr.next.next;
}
pre.next = null;
return slowptr;
}
}
我不清楚为什么ListNode left=mergeSort(head(；不是头整个原始ListNode不只是左半部分？
使用pre.next = null;，中间节点之前的节点的下一个节点被设置为null，因此在linkedList的前半部分(从head到pre，inklusiv(和后半部分(从middle到end，inklusif(之间不存在链接，因此它们变成了两个独立的列表。
以及为什么方法getMiddleNode只返回slowttr？
因为在循环之后，slowttr指向linkedList中间的节点。slowttr和fastptr被初始化为head；步行；浏览列表。但是fastptr的速度是slowttr的两倍(fastptr = fastptr.next.next;而不是slowptr = slowptr.next;(，所以当fastptr处于末尾时，slowttr已经完成了一半<>在中间。
您可以清楚地理解为什么ListNode left=mergeSort(head(只包含列表的左侧部分，通过在getMiddleNode(head(之后打印head
原因是在getMiddleNode(head(函数中将列表一分为二。当你通过递归一次又一次地做同样的事情时，你会得到列表的左半部分，它的边界是当前的中间，而右半部分正好相反(即，列表的右半部分，其边界是当前中间到当前最后一个元素(。
例如，假设这是您的初始列表，您希望在其中应用合并排序。11->8->3->35->4
在getMiddleNode(head(之后，您将得到如下两个列表：
11->8->3(左(和35->4(右(
现在，如果我们再次调用相同的函数，我们将得到：
11->8(左(和3(右([用于前左部分]
35和4(用于右前部分([用于右前]
现在，对于找到的上一个右部分基本情况，我们可以对其进行排序/交换，同样，前左部分的右侧也是如此，即3。
所以到目前为止，我们的名单是：3，4，35
如果我们在左上部分(11->8(的左上部分应用相同的逻辑，我们将得到：
11(左(和8(右(
现在，为当前列表再次找到了基本案例，所以我们可以对它们进行排序，最后我们会得到
3 4 8 11 35。
这就是传说中的合并排序的工作原理。