Leetcode基础刷题之PHP解析(147. Insertion Sort List）

/**

 * Definition for a singly-linked list.

 * class ListNode {

 *     public $val = 0;

 *     public $next = null;

 *     function __construct($val) { $this->val = $val; }

 * }

 */

class Solution {

​

    /**

     * @param ListNode $head

     * @return ListNode

     */

    function insertionSortList($head) {

        if(!$head || !$head->next) return $head;

        $p=$head->next;

        $head->next=null;

        while($p !==null){

            $pNext=$p->next;

            $q=$head;

            if($p->val<$q->val){

                $p->next=$q;

                $head=$p;

            }else{

                while($q !=null && $q->next !=null && $q->next->val<$p->val){

                    $q=$q->next;

                }

                $p->next=$q->next;

                $q->next=$p;

            }

            $p=$pNext;

        }

        return $head;

    }

}