148. Sort List

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


题目分析

一看到sort问题,而且时间复杂度要求又是O(n log n),很自然地就会想到Merge sort. Merge sort数组时,pseudo code如下:

func mergesort( var a as array )
    if ( n == 1 ) return a

    var l1 as array = a[0] ... a[n/2]
    var l2 as array = a[n/2+1] ... a[n]

    l1 = mergesort( l1 )
    l2 = mergesort( l2 )

    return merge( l1, l2 )
end func

func merge( var a as array, var b as array )
    var c as array

    while ( a and b have elements )
         if ( a[0] > b[0] )
              add b[0] to the end of c
              remove b[0] from b
         else
              add a[0] to the end of c
              remove a[0] from a
    while ( a has elements )
         add a[0] to the end of c
         remove a[0] from a
    while ( b has elements )
         add b[0] to the end of c
         remove b[0] from b
    return c
end func

(Reference: http://www.algorithmist.com/i... )

这道题要求是sort linked list,所以在上面pseudo code的基础上还要进行一些额外操作:

  1. 找到List的中点,使用快慢指针法。

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

    需要注意的是,找到中点后要把链表分成两段,即: slow.next = null;

  2. Merge两个链表。这部分代码应该近似于merge 2 sorted lists这道题的答案。


代码

/**
 * 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;
        }
        
        // find the mid point of the linked list
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode head2 = slow.next;
        slow.next = null;
        
        // if there's only 1 element in the list, continue splitting
        ListNode list1 = null;
        ListNode list2 = null;
        if (head != head2) {
            list1 = sortList(head);
            list2 = sortList(head2);
        }
        
        // merge 2 lists
        return mergeList(list1, list2);
        
    }
    
    // merge 2 lists. reference: Merge 2 Linked List
    public ListNode mergeList(ListNode head1, ListNode head2) {
        if (head1 == null) {
            return head2;
        }
        
        if (head2 == null) {
            return head1;
        }
        
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        while (head1 != null && head2 != null) {
            if (head1.val <= head2.val) {
                p.next = head1;
                p = p.next;
                head1 = head1.next;
            } else {
                p.next = head2;
                p = p.next;
                head2 = head2.next;
            }
        }
        
        if (head1 != null) {
            p.next = head1;
        }
        if (head2 != null) {
            p.next = head2;
        }
        
        return dummy.next;
    }
}

复杂度分析

时间复杂度 O(n log n)
空间复杂度 O(1)

评论

暂无评论