这个链表排序解决方案是如何工作的

Question

我正在处理一些leetcode问题，我不理解这个解决方案，也找不到答案，所以我需要澄清一下。问题是对链表进行排序。此解决方案使用合并排序方法。解决方案低于

class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode mid = getMid(head);
ListNode left = sortList(head);
ListNode right = sortList(mid);
return merge(left, right);
}
ListNode merge(ListNode list1, ListNode list2) {
ListNode dummyHead = new ListNode();
ListNode tail = dummyHead;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
tail.next = list1;
list1 = list1.next;
tail = tail.next;
} else {
tail.next = list2;
list2 = list2.next;
tail = tail.next;
}
}
tail.next = (list1 != null) ? list1 : list2;
return dummyHead.next;
}
ListNode getMid(ListNode head) {
ListNode midPrev = null;
while (head != null && head.next != null) {
midPrev = (midPrev == null) ? head : midPrev.next;
head = head.next.next;
}
ListNode mid = midPrev.next;
midPrev.next = null;
return mid;
}

}

所以在线上的sortList方法中

ListNode left = sortList(head);

这个作业是怎么做的？Head不是递增的，所以在每次递归调用中，它不是只是对同一个值一遍又一遍地调用方法吗？

我已经用手走过了这一步，在这里我被卡住了。

5 -> 3 -> 4
SortList(5)
head = 5 
mid = getMid(5) == 3
getMid(5)
mid prev = null    -> 5
head = 5           -> 4
mid = 3 
return 3 
left = sortList(5)
mid = getMid(5) = 3
left = sortList(5)
mid = sortList(5) = 3
left = sortList(5)

正如你所看到的，对于左边的每一项任务，都会有一个sortList(5(的调用。我很正派，但这个问题真的困扰着我。非常感谢所有的帮助！

Answer 1

它之所以有效，是因为getMid(head)将列表拆分为两个子列表。

在第一次调用getMid()之后，您有两个子列表：

head: 5
mid:  3 -> 4

调用第一个子列表上的sortList(head)会立即返回(因为head.next为空(

用第二个子列表调用sortList(mid)会将该列表拆分为另外两个子列表：

head': 3
mid': 4

在两个子列表上调用sortList也会立即返回(因为在这两个子列表中head.next都为null(。

然后，代码继续合并head'和mid'，这产生3 -> 4。

之后，列表head和上一次合并的结果(3 -> 4(合并在一起，这给出了最终结果：

3 -> 4 -> 5

---

我试着用一些图片更详细地解释。

这是对sortList(head):的第一次调用的列表

ListNode    ListNode    ListNode
head -> next     -> next     -> next     -> null
val: 5      val: 3      val: 4

getMid(head)更改列表并返回对中间元素的引用：

ListNode
head -> next     -> null
val: 5
ListNode    ListNode
mid  -> next     -> next     -> null
val: 3      val: 4

也就是说，虽然引用head本身没有改变，但它引用的列表因为head.next改变了而改变了！

如果我们用这个缩减列表调用sortList(head)，会发生什么？

sortList(head)中的第一个语句是

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

用缩减列表调用sortList(head)(二级(

ListNode
head -> next     -> null
val: 5

具有head.next == null，因此它立即返回head的值，并且在调用者中导致left被设置为head的值。

sortList()调用的第一级中的下一行是ListNode right = sortList(mid);。

列表拆分调用sortList(head)(二级(

ListNode    ListNode
mid  -> next     -> next     -> null
val: 3      val: 4

第一级中的mid现在被称为head(我称之为head'，以将其与第一级的head区分开来(

ListNode    ListNode
head' -> next     -> next     -> null
val: 3      val: 4

getMid(head)再次更改列表并返回对中间元素的引用：

ListNode
head' -> next     -> null
val: 3
ListNode
mid'  -> next     -> null
val: 4