Sort List leetcode java

题目：

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

题解：

考虑到要求用O(nlogn)的时间复杂度和constant space complexity来sort list，自然而然想到了merge sort方法。同时我们还已经做过了merge k sorted list和merge 2 sorted list。这样这个问题就比较容易了。

不过这道题要找linkedlist中点，那当然就要用最经典的faster和slower方法，faster速度是slower的两倍，当faster到链尾时，slower就是中点，slower的next是下一半的开始点。

解决了这些问题，题目就很容易解出了。

代码如下：

 1     public ListNode sortList(ListNode head) {

 2         if(head == null|| head.next == null)

 3             return head;

 4         ListNode slow = head, fast = head, firsthalf = head;

 5         while(fast.next!=null&&fast.next.next!=null){

 6             slow = slow.next;

 7             fast = fast.next.next;

 8         }

 9         ListNode secondhalf = slow.next;

         slow.next = null;

         

         ListNode leftlist = null, rightlist =null;

         if(firsthalf!=secondhalf){

             leftlist = sortList(firsthalf);

             rightlist = sortList(secondhalf);

         }

         return mergeTwoLists(leftlist, rightlist);

     }

     

     public ListNode mergeTwoLists(ListNode leftlist, ListNode rightlist){

         if(rightlist == null)

             return leftlist;

         if(leftlist == null)

             return rightlist;

         

         ListNode fakehead = new ListNode(-1);

         ListNode ptr = fakehead;

         while(rightlist!=null&&leftlist!=null){

             if(rightlist.val<leftlist.val){

                 ptr.next = rightlist;

                 ptr = ptr.next;

                 rightlist = rightlist.next;

             }else{

                 ptr.next = leftlist;

                 ptr = ptr.next;

                 leftlist = leftlist.next;

             }

         }

         

         if(rightlist!=null)

             ptr.next = rightlist;

         if(leftlist!=null)

             ptr.next = leftlist;

         

         return fakehead.next;

     }

巴特西

Sort List leetcode java

最新文章

热门文章