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

Revisions

  1. eric-zhu created this gist Nov 17, 2013.
    63 changes: 63 additions & 0 deletions sort_singly_linked_list
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,63 @@
    /**
    * 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;
    }
    }