148 Sort List

对于链表进行排序，要求时间复杂度为O(nlogn)，考虑使用二分的方法进行排序。如何将链表分成两个部分？使用之前常用的快慢指针的方法。

Python

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head:
            fast, slow = head, head
            pre = None
            while fast and fast.next:
                fast = fast.next.next
                pre = slow
                slow = slow.next
            if not pre:
                return head
            pre.next = None
            left = self.sortList(head)
            right = self.sortList(slow)
            p = dummy = ListNode(-1)
            while left and right:
                if left.val < right.val:
                    p.next = left
                    left = left.next
                else:
                    p.next = right
                    right = right.next
                p = p.next
            if left:
                p.next = left
            if right:
                p.next = right
            return dummy.next

Java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head != null){
            ListNode fast = head, slow = head;
            ListNode pre = null;
            while(fast != null && fast.next != null){
                fast = fast.next.next;
                pre = slow;
                slow = slow.next;
            }
            if(pre == null)
                return head;
            pre.next = null;
            ListNode left = this.sortList(head);
            ListNode right = this.sortList(slow);
            ListNode p = new ListNode(-1);
            ListNode dummy = p;
            while(left != null && right != null){
                if(left.val < right.val){
                    p.next = left;
                    left = left.next;
                }
                else { 
                    p.next = right;
                    right = right.next;
                }
                p = p.next;
            }
            if (left != null)
                p.next = left;
            if (right != null)
                p.next = right;
            return dummy.next;
        }
        else
            return null;
    }
}