重排链表【LC143】
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/reorder-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
最近是链表训练营
- 2022/09/22
- 2023/07/31
快慢指针+反转链表
类似9.回文链表*【LC234】
思路：首先找到链表的中间节点，然后将后半部分链表进行反转，然后将链表进行重组
实现
找到前半部分链表的尾节点
若链表有奇数个节点，则中间的节点看作是前半部分
计算链表节点的数量，然后遍历链表找到前半部分的尾节点
或者使用快慢指针：慢指针一次走一步，快指针一次走两步，快慢指针同时出发，当快指针移动到链表的末尾时，慢指针恰好到链表的中间；
反转后半部分链表
切断前后链表
合成链表
返回结果
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public void reorderList(ListNode head) { // 找到中间节点 ListNode end1 = findMiddlenode(head); // 反转后半部分节点 ListNode start2 = reverseList(end1.next); end1.next = null; // 拼接链表 ListNode p1 = head, p2 = start2; while (p2 != null){ ListNode tmp1 = p1.next, tmp2 = p2.next; p1.next = p2; p2.next = tmp1; p1 = tmp1; p2 = tmp2; } } public ListNode reverseList(ListNode head){ ListNode pre = null; ListNode cur = head; while (cur != null){ ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; } public ListNode findMiddlenode(ListNode head){ ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null){ // while (fast != null && fast.next != null){ 错误 // 当链表中只有两个节点时，慢指针会移动一步 slow = slow.next; fast = fast.next.next; } return slow; } }
- 复杂度分析
- 时间复杂度：O(N)，其中 N是链表中的节点数。
- 空间复杂度：O(1)
数组+双向指针
把链表放进数组中，然后通过双指针法，一前一后，来遍历数组，构造链表。
// 方法一 Java实现，使用数组存储节点 class Solution { public void reorderList(ListNode head) { // 双指针的做法 ListNode cur = head; // ArrayList底层是数组，可以使用下标随机访问 List<ListNode> list = new ArrayList<>(); while (cur != null){ list.add(cur); cur = cur.next; } cur = head; // 重新回到头部 int l = 1, r = list.size() - 1; // 注意左边是从1开始 int count = 0; while (l <= r){ if (count % 2 == 0){ // 偶数 cur.next = list.get(r); r--; }else { // 奇数 cur.next = list.get(l); l++; } // 每一次指针都需要移动 cur = cur.next; count++; } // 注意结尾要结束一波 cur.next = null; } }
- 复杂度分析
- 时间复杂度：O(N)，其中 N是链表中的节点数。
- 空间复杂度：O(N)
双向队列
把链表放进双向队列，然后通过双向队列一前一后弹出数据，来构造新的链表。这种方法比操作数组容易一些，不用双指针模拟一前一后了
// 方法二：使用双端队列，简化了数组的操作，代码相对于前者更简洁（避免一些边界条件） class Solution { public void reorderList(ListNode head) { // 使用双端队列的方法来解决 Deque<ListNode> de = new LinkedList<>(); // 这里是取head的下一个节点，head不需要再入队了，避免造成重复 ListNode cur = head.next; while (cur != null){ de.offer(cur); cur = cur.next; } cur = head; // 回到头部 int count = 0; while (!de.isEmpty()){ if (count % 2 == 0){ // 偶数，取出队列右边尾部的值 cur.next = de.pollLast(); }else { // 奇数，取出队列左边头部的值 cur.next = de.poll(); } cur = cur.next; count++; } cur.next = null; } }
- 复杂度分析
- 时间复杂度：O(N)，其中 N是链表中的节点数。
- 空间复杂度：O(1)
