重排链表
难度:
标签:
题目描述
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入：head = [1,2,3,4] 输出：[1,4,2,3]
示例 2：
输入：head = [1,2,3,4,5] 输出：[1,5,2,4,3]
提示：
- 链表的长度范围为
[1, 5 * 104] 1 <= node.val <= 1000
代码结果
运行时间: 108 ms, 内存: 23.1 MB
/*
题目思路：
使用Java Stream API进行链表处理的难度较大，因此我们以另一种方式实现。
1. 使用传统方法找到中间节点。
2. 反转后半部分链表。
3. 交替合并两个部分。
代码实现：
*/
// 由于Stream API不适合处理链表节点交换问题，因此没有使用Stream API的解决方案。解释
方法:
该题解的思路可以分为以下几个步骤：
1. 使用快慢指针找到链表的中点，将链表分为前后两个部分 l1 和 l2。
2. 反转后半部分链表 l2。
3. 将 l1 和反转后的 l2 依次连接，得到重排后的链表。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在使用快慢指针找链表中点时，如何确保当链表长度为奇数时，中点正确地指向中间节点而不是中间之前或之后的节点？
▷🦆
反转链表部分中，为何选择s.next作为新的链表l2的起点，而不是直接从s开始反转？
▷🦆
在合并链表的过程中，如果l1的长度大于l2的长度，最后一个节点的处理是否有特殊的考虑或步骤？
▷🦆
如果链表非常长，递归反转l2可能会导致栈溢出。是否有非递归的方法来反转链表？
▷