线性表
解题思路
因为链表不支持下标访问，所以无法随机访问链表中任意位置的元素；
因此比较容易想到的一个方法是，利用线性表存储该链表，然后利用线性表可以下标访问的特点，直接按顺序访问指定元素，重建该链表即可；
复杂度
-
时间复杂度：
O(N)，其中 N 是链表中的节点数； -
空间复杂度：
O(N)，其中 N 是链表中的节点数，主要为线性表的开销；
代码实现
var reorderList = function (head) {
// 1. 将链表放到数组里面
let list = [];
let curr = head;
while (curr) {
list.push(curr);
curr = curr.next;
}
// 2. 从头尾依次取一个相连接，头尾指针向中间移动
let left = 0;
let right = list.length - 1;
curr = head;
while (left < right) {
curr.next = list[left++];
curr = curr.next;
curr.next = list[right--];
curr = curr.next;
}
// 3. 当出现这种情况，说明节点是奇数个，直接将这个节点插入到链表的最后面
if (left === right) {
curr.next = list[left];
curr = curr.next;
}
// 4. 将链表最后一个节点的 next 指针指向 null，否则会是一个环状链表
curr.next = null;
};
寻找链表中点 + 链表逆序 + 合并链表
解题思路
第一步，将链表平均分成两半（寻找中间节点）
1 -> 2 -> 34 -> 5 -> 6第二步，将第二个链表逆序（反转链表）
1 -> 2 -> 36 -> 5 -> 4第三步，依次交替连接两个链表（合并链表）
1 -> 6 -> 2 -> 5 -> 3 -> 4
复杂度
-
时间复杂度：
O(N)，其中 N 是链表中的节点数； -
空间复杂度：
O(1)
代码实现
var reorderList = function (head) {
if (head == null) return;
// 1. 找到中间节点，将链表分割成两段
let mid = middleNode(head);
let l1 = head;
let l2 = mid.next;
mid.next = null;
// 2. 反转后面的链表
l2 = reverseList(l2);
// 3. 将两个链表合并起来
mergeList(l1, l2);
}
var middleNode = function (head) {
let slow = head;
let fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
var reverseList = function (head) {
let prev = null, curr = head, nextTemp = null;
while (curr != null) {
nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
var mergeList = function (l1, l2) {
let l1_tmp;
let l2_tmp;
while (l1 != null && l2 != null) {
l1_tmp = l1.next;
l2_tmp = l2.next;
l1.next = l2;
l1 = l1_tmp;
l2.next = l1;
l2 = l2_tmp;
}
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 25. K 个一组翻转链表
上一篇
评论
