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回答
因为在链表有两个节点的时候让 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。
继续加油
相似问题