题目

代码分析

按照数组归并排序的方式来完成链表，注意base case对于空的判断，快慢指针的应用

代码实现

class Solution {
    public ListNode sortList(ListNode head) {
        ListNode end=head;
        while(end!=null)
        {
            end=end.next;
        }
        return f(head,end);
    }

    public ListNode f(ListNode start,ListNode end)
    {
        if(start==null||start==end)
        {
            return start;
        }
        ListNode fast=start;
        ListNode slow=start;
        while(fast.next!=null&&fast.next.next!=null)
        {
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode temp=slow.next;
        slow.next=null;
        ListNode cur1=f(start,slow);
        if(fast.next!=null)
        {
            fast=fast.next;
        }
        ListNode cur2=f(temp,fast);
        ListNode res = merge(cur1, cur2);
        return res;
    }
    public ListNode merge(ListNode cur1,ListNode cur2)
    {
        ListNode res=new ListNode(-1);
        ListNode temp=res;
        ListNode next=null;
        while(cur1!=null&&cur2!=null)
        {
            if(cur1.val<cur2.val)
            {
                next=cur1.next;
                res.next=cur1;
                res=res.next;
                cur1=next;
            }else
            {
                next=cur2.next;
                res.next=cur2;
                res=res.next;
                cur2=next;
            }
        }
        if(cur1!=null)
        {
            res.next=cur1;
        }else if(cur2!=null)
        {
            res.next=cur2;
        }
        return temp.next;
    }
}

学习情况

1次