首页 > 代码库 > 148. Sort List

148. Sort List

Sort a linked list in O(n log n) time using constant space complexity.

虽然知道要用mergesort,也懂mergesort,但没有自己实现过。真正上手的时候就不回=。=。参考了discussion的思路。

思路:找到linkedlist中点,用快慢指针。快指针到终点的时候慢指针1.奇数在中点2.偶数在偏右一位。

例子:123. slow 2, fast 3 . 1234 slow 3 fast  null

然后要用另一个node来存中点前的node,来切割linkedlist。 123 -> 1 和 23 。 1234切割成 12 和 34.

然后merge,两个list比较。注意补node。  12结束循环,补上3node.  12循环结束补上3node。最后用dummy node把head node输出。一定要再实现一遍!!!

 
/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */public class Solution {    public ListNode sortList(ListNode head) {        if(head==null||head.next==null)        {            return head;        }        ListNode fast=head;        ListNode slow=head;        ListNode help=head;        while(fast!=null&&fast.next!=null)        {            help=slow;            slow=slow.next;            fast=fast.next.next;        }        help.next=null;        return mergesort(sortList(head),sortList(slow));    }    public ListNode mergesort(ListNode l1, ListNode l2)    {        if(l1==null)        {            return l2;        }        if(l2==null)        {            return l1;        }        ListNode dummy=new ListNode(0);        ListNode cur=dummy;        while(l1!=null&&l2!=null)        {            if(l1.val<l2.val)            {                cur.next=l1;                l1=l1.next;            }            else            {                cur.next=l2;                l2=l2.next;            }            cur=cur.next;        }        if(l1!=null)        {            cur.next=l1;        }        else        {            cur.next=l2;        }        return dummy.next;    }            }

 

148. Sort List