148. Sort List (Medium)

https://leetcode.com/problems/sort-list/

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

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

Solutions

class Solution {

    // Employ merge sort algorithm to solve this problem, be careful for the corn cases,

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        int len = 0;
        ListNode p = head;
        while (p != null) {
            len++;
            p = p.next;
        }

        // Find the middle position to split the list into two sub list
        int mid = 0;

        ListNode left = head;
        ListNode right = head.next;

        // Think it over if the len is odd or even
        while (mid < (len / 2 - 1)) {
            left = left.next;
            right = right.next;
            mid++;
        }

        // You must split it. This situation is totally different from those of using
        // array to hold elements.
        left.next = null;

        left = sortList(head);
        right = sortList(right);

        //merge

        // dummy head, easy for insertion
        ListNode dummy = new ListNode(-1);
        ListNode pointer = dummy;
        while (left != null && right != null) {
            if (left.val <= right.val) {
                pointer.next = left;
                left = left.next;
                pointer = pointer.next;
            } else {
                pointer.next = right;
                right = right.next;
                pointer = pointer.next;
            }
        }

        while (left != null) {
            pointer.next = left;
            pointer = pointer.next;
            left = left.next;
        }

        while (right != null) {
            pointer.next = right;
            pointer = pointer.next;
            right = right.next;
        }

        return dummy.next;
    }
}

Incorrect Solutions

References

Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2020-03-20 21:24:59

results matching ""

    No results matching ""