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

2019-9-9 星期一 开始吧

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


3c7adcc95595f991d38d94135ab9b37f.png


题目描述

给定一个单链表,按照规定的规则进行重新排序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

吴亲库里 has written 109 articles

情绪只是对自己无能的愤怒

积分:5267 等级:P8 职业:php 城市:杭州

0 条回复

登录后才能进行评论,立即登录?