leetcode 148 排序链表这一题

来源:1-1 什么是链表

mahsiaoko

2021-03-25 21:31:00

class Solution {
public ListNode sortList(ListNode head) {
if(head==null||head.next==null){
return head;
}

ListNode fast=head.next;
ListNode slow=head;
while(fast!=null && fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
ListNode head2=slow.next;
slow.next=null;
ListNode l1=sortList(head);
ListNode l2=sortList(head2);
return merge(l1,l2);
}

private ListNode merge(ListNode head1,ListNode head2){
if(head1==null||head2==null){
return head1==null?head2:head1;
}
ListNode dummyHead = new ListNode(0);
ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
while (temp1 != null && temp2 != null) {
if (temp1.val <= temp2.val) {
temp.next = temp1;
temp1 = temp1.next;
} else {
temp.next = temp2;
temp2 = temp2.next;
}
temp = temp.next;
}
temp.next=temp1==null?temp2:temp1;
return dummyHead.next;
}
}

这里,找中间节点时,使用的是这样的方式

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

我不是很明白 fast=head.next这种写法,我理解的是fast=head也可以,只要把链表分成两部分即可,但是fast=head的时候会报StackOverflowError这是为什么?希望老师解答一下。

写回答

1回答

liuyubobobo

2021-03-26

因为在链表有两个节点的时候让 fast = head链表没有分成两部分。


如果链表有两个节点比如 1->2

fast 是 1slow 是 1。

while 只执行一次。fast = fast.next.nextfast 指向空。slow = slow.nextslow 指向 2.


出了 while 循环head2 = slow.nexthead2 指向空。


所以最终结果head 指向 1head2 指向 2。相当于把 1->2 这个链表分成了 1->2 和 空 两部分。而 head 指向的链表和原链表一致链表没有更小。所以递归下去产生了无限递归stackoverflow。


继续加油

0

算法与数据结构

波波老师5年集大成之作,算法与数据结构系统学习,考试、面试、竞赛通用

2638 学习 · 1091 问题

查看课程