148. Sort List

Description

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

Solution

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) {
        return mergeSort(head);
    }
    
    public ListNode mergeSort(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode slow = head;
        ListNode fast = head.next;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode head2 = slow.next;
        slow.next = null;
        
        head = mergeSort(head);
        head2 = mergeSort(head2);
        
        return mergeSortedList(head, head2);
    }
    
    public ListNode mergeSortedList(ListNode p, ListNode q) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        
        while (p != null && q != null) {
            if (p.val <= q.val) {
                tail.next = p;
                p = p.next;
            } else {
                tail.next = q;
                q = q.next;
            }
            
            tail = tail.next;
        }
        
        if (p != null) {
            tail.next = p;
        } else {
            tail.next = q;
        }
        
        return dummy.next;
    }
}

Quick sort（TLE）

虽然会超时但是写起来也蛮有意思的。pivot自然选择head节点，比较tricky的地方是如何去移动节点。好实现的方式是将小于pivot的移动到当前链表的头部，但注意需要一个prev节点记录head之前的节点（防止链表被弄断啊），然后将节点插入到prev和firstHead之间。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        return quickSort(null, head, null);
    }

    public ListNode quickSort(ListNode prev, ListNode head, ListNode tail) {
        if (head == tail || head.next == tail) {
            return head;
        }

        ListNode fhead = head;
        ListNode curr = head;

        // compare curr.next not curr so we could spare a pre pointer
        while (curr.next != tail) { 
            if (curr.next.val < head.val) {     
                // move p to the between of prev and fhead
                ListNode p = curr.next;
                curr.next = p.next;
                p.next = fhead;
                if (prev != null) {
                    prev.next = p;
                }
                fhead = p;
            } else {
                curr = curr.next;
            }
        }

        quickSort(head, head.next, tail);
        return quickSort(prev, fhead, head);
    }
}