问题描述:
Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes' values.
For example,
Given {1,2,3,4}
, reorder it to {1,4,2,3}
.
原问题链接:https://leetcode.com/problems/reorder-list/
问题分析
在写具体的代码实现之前,我们先看问题的要求。它要求是将如L0, L1, L2...Ln的链表变成L0, Ln, L1, Ln-1...。这种样式相当于将链表从正中间拆分成两截。对于后面的那一截先反转一下。然后再将这两截链表按照顺序依次的加入元素,构成一个新的链表。
只要找到这个规律,后面的实现就有思路了。我们首先找到链表中间节点,因为要从它开始划分成两截。从实现的角度来说,我们可以用快慢指针的方式。当快指针到达链表末尾的时候,慢指针所在的位置就是分割点。在得到这个分割点之后,我们再将后面的这部分反转。关于反转的具体实现可以参考之前的讨论。
在反转完成之后,剩下的就是要考虑怎么实现两个链表的合并了。因为这里是轮流加入元素合并。我们的详细实现可以参照如下图的流程:
一开始,我们有两个链表first, second,我们额外声明一个变量next:
在下一步的时候,我们实现元素的交叠:
它的作用相当于实现second.next = first.next; first.next = second; 然后我们再确定下一步first, second的位置:
这种调整相当于如下的代码:first = second.next; second = next; 这样,我们就完成了一个元素交叠的过程。我们通过循环上述的过程就可以实现最终的交叠。
结合上述的讨论,详细的代码实现如下:
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public void reorderList(ListNode head) { if(head == null || head.next == null) return; ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode first = head; ListNode half = slow.next; slow.next = null; half = reverse(half); while(first != null && half != null) { ListNode next = half.next; half.next = first.next; first.next = half; first = half.next; half = next; } } private ListNode reverse(ListNode node) { ListNode tmp = null, pre = null; while(node != null) { tmp = node; node = node.next; tmp.next = pre; pre = tmp; } return tmp; } }
相关推荐
正确的姿势,学习的态度来刷 LeetCode:高效的代码、简洁的注释、精炼的总结。
leetcode 非官方顺序leetcode题解,主要代码为Python和C++。 leetcode 第1题: leetcode 第2题: leetcode 第3题: leetcode 第4题: leetcode 第5题: leetcode 第6题: leetcode 第7题: leetcode 第9题: ...
leetcode11 top 1. 位运算 LeetCode191 : 二进制位1的个数 LeetCode338 : 比特位运算 2. 字典树 LeetCode209 : 实现一个Trie结构 LeetCode79 : 单词搜索(判断单词是否出现在给定的网格中) LeetCode212 : 单词搜索II...
LeetCode::laptop:LeetCode解决方案
leetcode 答案 leetCode :keyboard:我的 Leetcode 解题答案
lru缓存leetcode 力码 涵盖了 Geeks for Geeks 和 Leet Code 的各种问题。 LeetCode 1 : 二和 (46_Easy) LeetCode 2 : 两个数字相加 (96_Medium) LeetCode 3 : 无重复字符的最长子串 (214_Medium) LeetCode 4 : 两个...
LeetCode 在LeetCode和其他编码平台上解决的问题的集合
leetcode :ice_cream: LeetCode Kindem 的个人 LeetCode 题解仓库,欢迎交流学习。 下面的目录中 $number 题号代表经典 LeetCode 题目,$number.$number 题号表示 LeetCode 面试题。 :receipt: 目录 统计 值 AC 的...
leetcode 分类 LeetCode :bouquet::bouquet::bouquet: 介绍 leetcode 题解,Issues 会记录 leetcode 解题之路,并使用 label 进行了分类。 目录 链表
Leetcode:Leetcode提交
LeetCode 101:和你一起你轻松刷题(C++)
:fire: Leetcode :fire: 实践使完美 :party_popper: 开玩笑的单元测试 :sparkles: 简单的代码 :artist_palette: 可读代码 入门指南 git clone https: //github.com/tangweikun/leetcode.git cd leetcode npm ...
idea中leetcode插件Rust 中的 LeetCode 解决方案 怎么跑?...,所有解决方案代码都在leetcode::leetcode::editor::en并重用于leetcode 。 它有一个全局结构Solution ,所有解决方案条目都在其中实现。
leetcode:leetcode刷题
LeetCode:LeetCode的代码
Leetcode:LeetCode解题代码
LeetCode:LeetCode的注释
leetcode:LeetCode问题
加油站问题leetcode LeetCode LeetCode-JS分类列表: :smiling_face_with_smiling_eyes: :flushed_face: :winking_face: :face_with_tongue: :face_with_open_mouth: :beaming_face_with_smiling_...
leetcode:LeetCode题解