LeetCode148--排序链表

古城微笑少年丶 2023-01-16 14:28 188阅读 0赞

### 题目分析 ###

**时间复杂度限制下，符合要求的常规排序算法可以用快速，归并.....来完成，这里使用的是归并排序，归并排序最重要的的就是合并操作了，而且他合并的是两个有序集，对于当前的链表来说，只有当链表只有一个结点的时候，此链表才是有序链表。不断的拆分链表，这是递，当拆分的两个链表都只剩下一个结点时，merge，然后回到上一层继续合并，这是归。所以每一次回来合并的都是有序链表。**

/**
     * 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 sortList($head) {
            if(!$head || !$head->next) return $head;
            $slow=$fast=$head;
            while($fast && $fast->next){
                $pre=$slow;
                $fast=$fast->next->next;
                $slow=$slow->next;
            }
            $pre->next=null;
            return $this->merge($this->sortlist($head),$this->sortlist($slow));
        }
        
        function merge($l1,$l2){
            $node=new ListNode(-1); //随意塞入一个数字作为新链表头，最后取next即可。
            $cur=$node;
            while($l1 && $l2){
                if($l1->val>$l2->val){
                    $cur->next=$l2;
                    $l2=$l2->next;
                }else{
                    $cur->next=$l1;
                    $l1=$l1->next;
                }
                $cur=$cur->next;
            }
            
            if($l1){
                $cur->next=$l1;
            }
            if($l2){
                $cur->next=$l2;
            }
            return $node->next;
        }
    }