148. 排序链表

题意：

解题思路：

思路：
1. 快速排序 Time: O(n*logn), Space: O(n)
2. 归并排序 Time: O(n*logn) Space: O(logn)

PHP代码实现：

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {
    /**
     * @param ListNode $head
     * @return ListNode
     */
    function sortList($head) {
        /*$this->quickSort($head, null);
        return $head;*/
        if ($head == null || $head->next == null) return $head;
        $slow = $head; $fast = $head;
        while ($fast->next != null && $fast->next->next != null) {
            $slow = $slow->next;
            $fast = $fast->next->next;
        }
        $tail = $slow->next;
        $slow->next = null;
        $left = $this->sortList($head);
        $right = $this->sortList($tail);
        return $this->mergeTwoList($left, $right);
    }
    function mergeTwoList($l1, $l2) {
        $dummy = new ListNode(0);
        $cur = $dummy;
        while ($l1 != null && $l2 != null) {
            if ($l1->val < $l2->val) {
                $cur->next = $l1;
                $l1 = $l1->next;
            } else {
                $cur->next = $l2;
                $l2 = $l2->next;
            }
            $cur = $cur->next;
        }
        $cur->next = $l1 == null ? $l2 : $l1;
        return $dummy->next;
    }
    function quickSort($head, $end) {
        if ($head == $end || $head->next == $end) return;
        $pivot = $head->val;
        $slow = $head;
        $fast = $head->next;
        while ($fast != $end) {
            if ($fast->val <= $pivot) {
                $slow = $slow->next;
                $this->swap($slow, $fast);
            }
            $fast = $fast->next;
        }
        $this->swap($head, $slow);
        $this->quickSort($head, $slow);
        $this->quickSort($slow->next, $end);
    }
    function swap(&$a, &$b) {
        $temp = $a->val;
        $a->val = $b->val;
        $b->val = $temp;
    }
}

GO代码实现：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
    quickSort(head, nil)
    return head
}
func swap(a, b *ListNode) {
    a.Val, b.Val = b.Val, a.Val
}
func quickSort(head, end *ListNode) {
    if head == end || head.Next == end {
        return
    }
    pivot := head.Val
    slow, fast := head, head.Next
    for fast != end {
        if fast.Val <= pivot {
            slow = slow.Next
            //swap(slow, fast)
            slow.Val, fast.Val = fast.Val, slow.Val
        }
        fast = fast.Next
    }
    //循环结束后交换头节点和慢指针指向的值,把pivot放在大小两堆数值的中间
    //swap(head, slow)
    slow.Val, head.Val = head.Val, slow.Val
    quickSort(head, slow)   // 递归处理pivot左右两边的链表
    quickSort(slow.Next, end)
}

// 单链表归并排序 Time: O(n*logn) Space: O(logn)
func mergeSortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    slow, fast := head, head // 快慢指针初始化在链表头
    for fast.Next != nil && fast.Next.Next != nil {
        slow = slow.Next      // 慢指针一次走一步
        fast = fast.Next.Next // 快指针一次走两步
    }
    // 循环结束后慢指针指向的是前一半链表的最后一个元素
    right := mergeSortList(slow.Next)       // 先排序后一段链表
    slow.Next = nil                         // 然后把慢指针的Next置为空指针
    left := mergeSortList(head)             // 再排序前一段链表
    return mergeTwoSortedLists(left, right) // 合并排序后的两段链表
}
func mergeTwoSortedLists(l1, l2 *ListNode) *ListNode {
    dummy := new(ListNode)
    p := dummy
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            p.Next = l1
            l1 = l1.Next
        } else {
            p.Next = l2
            l2 = l2.Next
        }
        p = p.Next
    }
    if l1 != nil {
        p.Next = l1
    }
    if l2 != nil {
        p.Next = l2
    }
    return dummy.Next
}