算法:99.重排链表

https://www.lintcode.com/problem/reorder-list/description

描述

给定一个单链表L:L→L1→…→Ln-1→Ln,

重新排列后为:L→Ln→L1→Ln-1→L2→Ln-2→…

必须在不改变节点值的情况下进行原地操作。

样例

给出链表,重新排列后为。

思路

一个简洁的实现,直接的思路,每次查找最后一个节点,插入现在的节点后面。

上面这个实现算是非常简洁了,不过效率较低,每次都要搜索一下最后的节点。

注意边界的处理,对 lastNode 的空值判断。

一个更高效的版本:

在这个实现中,整体分为三部分,第一步,查找链表的中点,第二步,翻转链表的后半部分。第三步,合并两个链表。

节点在处理时一定要注意边界的情形,对next字段也需要仔细处理,防止形成环造成死循环。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180823G1NL9B00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码关注腾讯云开发者

领取腾讯云代金券