143.md

✏️Leetcode基础刷题之(143. Reorder List143)

2019-09-09 吴亲库里 库里的深夜食堂

---

✏️描述

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

---

联系

​