147. 对链表进行插入排序

题意：

解题思路：

思路：[遍历n个节点，每个节点遍历n次，时间复杂度O(n2)]
1. 定义虚拟dummy节点，指向头节点，定义头节点为cur；
2. 扫描链表，前后节点进行比较，如果前面元素u小于后面p->next，v，则需要把u插入到p后面，v前面:p->next = 2 ,插入0 => [p->next = 0, 0->next = 2] => p->0->2;
3. 直到最后节点为空退出；

PHP代码实现：

/**
 * 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) {
        $dummy = new ListNode(0);
        $cur = $head;
        while ($cur != null) {
            $next = $cur->next;
            $p = $dummy;
            while ($p->next != null && $cur->val >= $p->next->val) {
                $p = $p->next;
            }
            $cur->next = $p->next;
            $p->next = $cur;
            $cur = $next;
        }
        return $dummy->next;
    }
}

GO代码实现：

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func insertionSortList(head *ListNode) *ListNode {
    dummy := &ListNode{}
    cur := head
    for cur != nil {
        next := cur.Next
        p := dummy
        for p.Next != nil && cur.Val >= p.Next.Val {
            p = p.Next
        }
        cur.Next = p.Next
        p.Next = cur
        cur = next
    }
    return dummy.Next
}