Leetcode基础刷题之PHP解析(143. Reorder List）

2019-9-9 星期一 开始吧

上一题链接Leetcode基础刷题之PHP解析(139. Word Break）

题目描述

给定一个单链表，按照规定的规则进行重新排序L0->Ln->L1->Ln-1....题目的要求是你不能直接在链表上修改对应的值。需要通过改变他的next指针来完成。

题目分析

这道题有点难度，其实个人觉得链表的操作并不简单，稍不留神，你的next指针就不知道指向哪里了。这道题要分几步解，首先利用快慢指针找出链表中间的点，从中间点开始切割，把链表右半部分进行翻转，再把翻转的部分间隔插回第一个链表，完成。

代码实现

    /**
     * @param ListNode $head
     * @return NULL
     */
    function reorderList($head) {
        if(!$head || !$head->next || !$head->next->next) return ;
        $fast=$head;
        $slow=$head;
        while($fast !=null && $fast->next !=null){ //找出中间点
            $fast=$fast->next->next;
            $slow=$slow->next;
        }
        $middle=$slow->next;
        $slow->next=null;
        $last=$middle;
        $pre=null;
        while($last){ //翻转右半部分链表
            $node=$last->next;
            $last->next=$pre;
            $pre=$last;
            $last=$node;
        }
        
        while($head && $pre){ //间隔插入
            $next=$head->next;
            $head->next=$pre;
            $pre=$pre->next;
            $head->next->next=$next;
            $head=$next;
        }
        
    }

写的不够优雅，可以改进一下。

Github整理地址:https://github.com/wuqinqiang/leetcode-php