148 Sort List

148. Sort List

1. Question

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

2. Implementation

(1) Top down merge sort

/**
 * 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 || head.next == null) {
            return head;
        }

        ListNode slow = head, fast = head;

        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode p = slow.next;
        slow.next = null;

        ListNode l1 = sortList(head);
        ListNode l2 = sortList(p);

        return merge(l1, l2);
    }

    public ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curNode = dummy;

        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curNode.next = l1;
                l1 = l1.next;
            }
            else {
                curNode.next = l2;
                l2 = l2.next;
            }
            curNode = curNode.next;
        }

        while (l1 != null) {
            curNode.next = l1;
            l1 = l1.next;
            curNode = curNode.next;
        }

        while (l2 != null) {
            curNode.next = l2;
            l2 = l2.next;
            curNode = curNode.next;
        }

        return dummy.next;
    }
}

(2) Bottom up merge sort

/**
 * 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 || head.next == null) {
            return head;
        }

        int len = 0;
        ListNode curNode = head;

        while (curNode != null) {
            curNode = curNode.next;
            ++len;
        }

        ListNode left = null, right = null, tail = null, dummy = null;
        for (int step = 1; step < len; step *= 2) {
            dummy = new ListNode(0);
            curNode = head;
            tail = dummy;

            while (curNode != null) {
                left = curNode;
                right = split(left, step);
                curNode = split(right, step);
                tail = merge(left, right, tail);
            }
            head = dummy.next;
        }
        return head;
    }

    // Split a linked list into half, where the first half contains n nodes (or all nodes)
    // Return the head of the second half list (or null)
    public ListNode split(ListNode head, int n) {
        for (int i = 1; head != null && i < n; i++) {
            head = head.next;
        }

        if (head == null) {
            return null;
        }
        ListNode second = head.next;
        head.next = null;
        return second;
    }

    // Merge two sorted linked list l1 and l2
    // Append the result to list node tail
    // Return the tail of merge sorted list
    public ListNode merge(ListNode l1, ListNode l2, ListNode tail) {
        ListNode curNode = tail;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curNode.next = l1;
                l1 = l1.next;
            }
            else {
                curNode.next = l2;
                l2 = l2.next;
            }
            curNode = curNode.next;
        }

        curNode.next = l1 == null ? l2 : l1;
        while (curNode.next != null) {
            curNode = curNode.next;
        }
        return curNode;
    }
}

3. Time & Space Complexity

Top down merge sort：时间复杂度O(nlogn), 空间复杂度O(logn)

Bottom up merge sort: 时间复杂度O(nlogn), 空间复杂度O(1)