LeetCoder - Sort List

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

/**
 * 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;
        while(fast.next!=null && fast.next.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        fast = slow;
        slow = slow.next;
        fast.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(slow);
        fast = head;
        return merge(left, right);
    }
 
    public ListNode merge(ListNode n1, ListNode n2) {
        if(n1==null) {
            return n2;
        }
        if(n2==null) {
            return n1;
        }
        ListNode h = null;
        if(n1.val<n2.val) {
            h = n1;
            n1 = n1.next;
        } else {
            h = n2;
            n2 = n2.next;
        }
        ListNode cur = h;
        while(!(n1==null && n2==null)) {
            if(n1==null || (n2!=null && n1.val>n2.val)) {
                cur.next = n2;
                n2 = n2.next;
            } else {
                cur.next = n1;
                n1 = n1.next;
            }
            cur = cur.next;
        }
        return h;
    }
}


public class Solution {
    public ListNode sortList(ListNode head) {
       
        if(head==null || head.next==null) return head;
        ListNode p1 = head;
        ListNode p2 = head;
        while(p2.next!=null && p2.next.next!=null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        ListNode head2 = p1.next;
        p1.next = null;
       
        ListNode h1 = sortList(head);
        ListNode h2 = sortList(head2);
       
        return merge(h1, h2);
    }
   
    public ListNode merge(ListNode h1, ListNode h2) {
        ListNode dummyNode = new ListNode(0);
        ListNode p0 = dummyNode;
        ListNode p1 = h1;
        ListNode p2 = h2;
       
        while(p1!=null || p2!=null) {
            if(p2==null || (p1!=null && p1.val<p2.val)) {
                p0.next = p1;
                p1 = p1.next;
            } else {
                p0.next = p2;
                p2 = p2.next;
            }
            p0 = p0.next;
        }
        return dummyNode.next;
       
    }
}


=========

/**
 * 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[] parts = splitList(head);
        ListNode h1 = sortList(parts[0]);
        ListNode h2 = sortList(parts[1]);
        return merge(h1, h2);
    }
   
    private ListNode[] splitList(ListNode head) {
        ListNode[] res = new ListNode[2];
        if (head == null) {
            return res;
        }
        res[0] = head;
        ListNode p1 = head;
        ListNode p2 = head;
        while (p2 != null && p2.next != null && p2.next.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        res[1] = p1.next;
        p1.next = null;
        return res;
    }
   
    private ListNode merge(ListNode node1, ListNode node2) {
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        ListNode p1 = node1;
        ListNode p2 = node2;
        while (p1 != null || p2 != null) {
            if (p1 == null || (p2 != null && p2.val < p1.val)) {
                p.next = p2;
                p2 = p2.next;
            } else {
                p.next = p1;
                p1 = p1.next;
            }
            p = p.next;
        }
        return dummy.next;
    }

}