143. 重排链表
143. 重排链表
题目
You are given the head of a singly linked-list. The list can be represented as:
L0 -> L1 -> … -> Ln - 1 -> Ln
Reorder the list to be on the following form:
L0 -> Ln -> L1 -> Ln - 1 -> L2 -> Ln - 2 -> …
You may not modify the values in the list's nodes. Only nodes themselves may be changed.
Example 1:
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Example 2:
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Constraints:
- The number of nodes in the list is in the range
[1, 5 * 10^4]
. 1 <= Node.val <= 1000
题目大意
按照指定规则重新排序链表:第一个元素和最后一个元素排列在一起,接着第二个元素和倒数第二个元素排在一起,接着第三个元素和倒数第三个元素排在一起。
解题思路
最近简单的方法是先把链表存储到数组里,然后找到链表中间的结点,按照规则拼接即可,但这样时间复杂度是 O(n)
,空间复杂度是 O(n)
。
更好的做法是结合之前几道题的操作:链表逆序,找中间结点。
先找到链表的中间结点,然后利用逆序区间的操作,如 第 92 题 里的 reverseBetween()
操作,只不过这里的反转区间是从中点一直到末尾。最后利用 2 个指针,一个指向头结点,一个指向中间结点,开始拼接最终的结果。
复杂度分析
- 时间复杂度:
O(n)
,其中n
是链表的长度。 - 空间复杂度:
O(1)
,使用了常数级别的额外空间。
代码
/**
* @param {ListNode} head
* @return {void} Do not return anything, modify head in-place instead.
*/
var reorderList = function (head) {
if (!head || !head.next) return head;
// 寻找中间节点
let slow = head;
let fast = head;
while (fast && fast.next && fast.next.next) {
slow = slow.next;
fast = fast?.next?.next;
}
// 反转后一半链表,eg: 1->2->3->4->5->6 to 1->2->3->6->5->4
const middle = slow;
let cur = middle.next;
while (cur.next) {
let temp = cur.next;
cur.next = temp.next;
temp.next = middle.next;
middle.next = temp;
}
// 按要求重新拼接链表,eg: 1->2->3->6->5->4 to 1->6->2->5->3->4
let p3 = head;
let p4 = middle.next;
while (p3 != middle) {
middle.next = p4.next;
p4.next = p3.next;
p3.next = p4;
p3 = p4.next;
p4 = middle.next;
}
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
2095 | 删除链表的中间节点 | 链表 双指针 | ||
2516 | 每种字符至少取 K 个 | 哈希表 字符串 滑动窗口 |