124. Sort List

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