leetCode ✏Leetcode基础刷题之(143. Reorder List143)
✏描述
给定一个单链表，按照规定的规则进行重新排序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;
}
}
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)