https://www.lintcode.com/problem/reorder-list/description
描述
给定一个单链表L:L→L1→…→Ln-1→Ln,
重新排列后为:L→Ln→L1→Ln-1→L2→Ln-2→…
必须在不改变节点值的情况下进行原地操作。
样例
给出链表,重新排列后为。
思路
一个简洁的实现,直接的思路,每次查找最后一个节点,插入现在的节点后面。
上面这个实现算是非常简洁了,不过效率较低,每次都要搜索一下最后的节点。
注意边界的处理,对 lastNode 的空值判断。
一个更高效的版本:
在这个实现中,整体分为三部分,第一步,查找链表的中点,第二步,翻转链表的后半部分。第三步,合并两个链表。
节点在处理时一定要注意边界的情形,对next字段也需要仔细处理,防止形成环造成死循环。
领取专属 10元无门槛券
私享最新 技术干货