Skip to content

Instantly share code, notes, and snippets.

@eric-zhu

eric-zhu/sort_singly_linked_list

Created November 17, 2013 23:55
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save eric-zhu/7520006 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save eric-zhu/7520006 to your computer and use it in GitHub Desktop.
Download ZIP
Sort a linked list in O(n log n) time using constant space complexity.
Raw
sort_singly_linked_list
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
// Time: O(nlogn) Space: O(logn) because of the recursion.
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) return head;
// Split list into two halves.
ListNode firstHalfEnd = findHalf(head);
ListNode secondHalfStart = firstHalfEnd.next;
firstHalfEnd.next = null;
// Merge two halves.
return merge(sortList(head), sortList(secondHalfStart));
}
// Merge two lists.
private ListNode merge(ListNode head1, ListNode head2) {
ListNode dummyHead = new ListNode(-1);
ListNode cur = dummyHead;
ListNode cur1 = head1, cur2 = head2;
// Append the smaller one to the new list.
while (cur1 != null && cur2 != null) {
if (cur1.val < cur2.val) {
cur.next = cur1;
cur1 = cur1.next;
} else {
cur.next = cur2;
cur2 = cur2.next;
}
cur = cur.next;
}
// Append the remainder.
if (cur1 == null) {
cur.next = cur2;
} else {
cur.next = cur1;
}
return dummyHead.next;
}
// Assume the list has at least two nodes.
private ListNode findHalf(ListNode head) {
ListNode slow = head;
ListNode fast = head;
// Advance the fast pointer when next node is available.
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
@eric-zhu
Copy link
Copy Markdown
Author

eric-zhu commented Nov 18, 2013 

public class Solution {
    // Time: O(nlogn) Space: O(1).
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode dummy = new ListNode(-1);// Point to the merged list.
        ListNode oldDummy = new ListNode(-1);// Point to the non-merged list.
        ListNode tmpDummy = new ListNode(-1);// Point to the temporary merged list.
        oldDummy.next = head;

        int listLen = getListLen(head);
        for (int i = 1; i < listLen; i <<= 1) {
            // Merge 2^i nodes each loop.
            mergeSort(oldDummy, dummy, tmpDummy, i);
        }
        return dummy.next;
    }

    private void mergeSort(ListNode oldDummy, ListNode dummy, ListNode tmpDummy, int subListLen) {
            dummy.next = null;
            ListNode mergedTail = null;
            while (oldDummy.next != null) {
                // Split lists into sublists with i nodes.
                ListNode head1 = getNewListHead(oldDummy, subListLen);
                ListNode head2 = getNewListHead(oldDummy, subListLen);

                // Merge lists. Use tmpDummy to store the head, and
                // return the tail for next appending.
                ListNode tail = merge(tmpDummy, head1, head2);
                if (dummy.next == null) {
                    dummy.next = tmpDummy.next;
                } else {
                    // Append merged list.
                    mergedTail.next = tmpDummy.next;
                }
                mergedTail = tail;
            }
            // Next loop the merged list will be used for further merging.
            oldDummy.next = dummy.next;
    }

    private ListNode getNewListHead(ListNode oldDummy, int subListLen) {
        ListNode cur = oldDummy.next;
        if (cur == null) return cur;
        updateOldHead(oldDummy, subListLen);
        return cur;
    }

    private void updateOldHead(ListNode oldDummy, int subListLen) {
        ListNode cur = oldDummy.next;
        if (cur == null) return;

        // Update the old dummy.
        for (int i = 1; i < subListLen && cur.next != null; ++i) {
            cur = cur.next;
        }

        oldDummy.next = cur.next;
        // Cut the previous list.
        cur.next = null;
    }

    private ListNode merge(ListNode tmpDummy, ListNode head1, ListNode head2) {
        ListNode cur = tmpDummy;
        ListNode cur1 = head1, cur2 = head2;
        while (cur1 != null && cur2 != null) {
            if (cur1.val < cur2.val) {
                cur.next = cur1;
                cur1 = cur1.next;
            } else {
                cur.next = cur2;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }
        if (cur1 != null) {
            cur.next = cur1;
        } else {
            cur.next = cur2;
        }
        // Move to tail for appending.
        while (cur.next != null) cur = cur.next;

        return cur;// The current tail.
    }

    private int getListLen(ListNode head) {
        ListNode cur = head;
        int count = 0;
        while (head != null) {
            head = head.next;
            ++count;
        }
        return count;
    }
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment