题解 | #单链表的排序#

<?php

/*class ListNode{
    var $val;
    var $next = NULL;
    function __construct($x){
        $this->val = $x;
    }
}*/

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 the head node
 * @return ListNode类
 */
function sortInList( $head )
{
    if($head == null || $head->next == null){
        return $head;
    }
    // 使用快慢指针找到中间节点
    $slow = $head;
    $fast = $head->next;
    while($fast != null && $fast->next != null){
        $slow = $slow->next;
        $fast = $fast->next->next;
    }
    // 分割成左右两个链表
    $newList = $slow->next;
    $slow->next = null;
    printf("new: ".$newList->val."\n");
    printf($head->val."\n");
    // 递归
    $left = sortInList($head);
    $right = sortInList($newList);
    // 归并排序
    $ret = null;
    $retHead = null;
    while($left != null && $right != null){
        if($left->val <= $right->val){
            $temp = new ListNode($left->val);
            $left = $left->next;
        }else{
            $temp = new ListNode($right->val);
            $right = $right->next;
        }
        if($ret == null){
            $ret = $temp;
            $retHead = $temp;
        }else{
            $ret->next = $temp;
            $ret = $ret->next;
        }
    }
    // 判断是否有链表剩下
    $left == null ? $ret->next = $right : $ret->next = $left;
    return $retHead;
}

方法一：直接把所有链表的值读到array里，用sort，然后再把值放回链表里

方法二：归并排序法（含递归）

1. 如果head ==null 或者head->next == null，直接返回head
2. 快慢指针法找到链表的中点，根据中点分割成两个链表。注意！！slow = head，fast = head->next，这样才能处理只有两个节点的链表
3. 递归分割链表：left = sort（head），right = sort（newHead（右链表的新头））
4. 归并排序，左右两个链表合成1个新的有序链表并返回