切换主题
反转链表篇
整表反转
迭代法
解题思路
- 若表为
null或长为1，直接返回表头head； - 初始
[prev, curr] = [null, head]，当curr不为空时，局部依次交换节点直到反转完成。
JavaScript
const reverseList = head => {
if (!head || !head.next) return head
let [prev, curr] = [null, head]
while (curr) {
const next = curr.next // 获取下一节点
curr.next = prev // 局部反转
prev = curr // 缓存当前节点
curr = next // 更新当前节点
}
return prev
}时间复杂度：O(n)；空间复杂度：O(1)。
递归法
解题思路
先局部反转head.next.next = head，再切断进栈前的连接head.next = null，避免成环。
JavaScript
const reverseList = head => {
if (!head || !head.next) return head
const newHead = reverseList(head.next)
head.next.next = head // 出栈时，将当前节点连接至上一节点（局部反转）
head.next = null // 切断当前节点进栈时的连接，防止循环引用
return newHead
}
/*
假设初始链表为：1->2->3->4
递归时，在递的过程中，当递到尾节点 （head === 4） 时，
开始递归中的归，此时依次返回的head为4，3，2，1
head.next.next = head 即 4.next.next = 4 (局部反转 5.next = 4)
*/时间复杂度：O(n)；空间复杂度：O(n)。
区间反转
穿针引线法
解题思路
首先设置虚拟头节点dummy：
- 从
prev = dummy开始，先迭代l-1步找到l对应的节点left及前一节点prev； - 再迭代
r-l+1步找到r对应的节点right及right.next，然后从原链切出区间[left, right]； - 将区间
[left, right]反转后，重新拼接成链。
返回 dummy.next。
JavaScript
const reverseBetween = (head, l, r) => {
const dummy = new ListNode(-1, head)
let prev = dummy
// 遍历 l-1 步找到 l 的前驱节点
let cnt = l
while (cnt-- > 1) {
prev = prev.next
}
// 待反转区间[left, right]
let [left, right, k] = [prev.next, prev, r - l + 1]
while (k-- > 0) {
right = right.next
}
let curr = right.next
// 切出区间
prev.next = null
right.next = null
// 做反转，并拼接
prev.next = reverseList(left)
left.next = curr
return dummy.next
}时间复杂度：O(n)；空间复杂度：O(1)。
头插法
解题思路
首先设置虚拟头节点dummy，在需要反转的区间里，每遍历到一个节点，让这个新节点来到反转部分的起始位置，我们使用三个指针变量prev、curr、next 来记录反转的过程中需要的变量，它们的意义如下：
curr：指向待反转区域的第一个节点l；next：永远指向curr的下一个节点，循环过程中，curr变化以后next会变化；prev：永远指向待反转区域的第一个节点l的前一个节点，在循环过程中不变。
具体操作步骤：
- 先将
curr的下一个节点记录为next； - 把
curr的下一个节点指向next的下一个节点； - 把
next的下一个节点指向prev的下一个节点； - 把
prev的下一个节点指向next。
返回 dummy.next。
JavaScript
const reverseBetween = (head, l, r) => {
const dummy = new ListNode(-1, head)
let prev = dummy
// 遍历 l-1 步找到 l 的前驱节点
let cnt = l
while (cnt-- > 1) {
prev = prev.next
}
// 反转区间[l, r]
let [curr, k] = [prev.next, r - l]
while (k-- > 0) { // 头插法
const next = curr.next // 步骤1
curr.next = next.next // 步骤2
next.next = prev.next // 步骤3
prev.next = next // 步骤4
}
return dummy.next
}时间复杂度：O(n)；空间复杂度：O(1)。
K个一组反转
穿针引线法（K个一组）
解题思路
设置虚拟头节点dummy，迭代K次，找到该组最后一个节点last，判断当前last是否为空：
- 为空则跳出
break； - 否则缓存
K组的开始节点及其下一节点并切断链表let [curr, next] = [prev.next, last.next]; last.next = null， 然后反转K组节点并拼接，最后更新节点prev = curr;last = prev;。
返回dummy.next。
JavaScript
const reverseKGroup = (head, k) => {
const dummy = new ListNode(-1, head)
let [prev, last] = [dummy, dummy]
while (last.next) { // k个一组
for (let i = 0; i < k && last != null; i++) {
last = last.next
}
if (last == null) break
// 区间反转
let [curr, next] = [prev.next, last.next]
last.next = null // 切断
prev.next = reverseList(curr)
curr.next = next
// 更新至下一区间
prev = curr
last = prev
}
return dummy.next
}时间复杂度：O(k*n)；空间复杂度：O(1)。
偶数长度反转
迭代法
解题思路
设置虚拟头节点dummy，在迭代中从0开始计算链表节点数cnt及当前组的节点数len，并判断len的奇偶性len & 1：
- 当
len为奇数，则以len区间，直接更新节点curr = curr.next; prev = prev.next跳过当前组； - 当
len为偶数，则以len区间，头插法反转该组子链表并更新节点prev = curr;curr = curr.next。
返回dummy.next。
JavaScript
const reverseEvenLengthGroups = head => {
const dummy = new ListNode(-1, head)
let [prev, curr, cnt] = [dummy, dummy.next, 0]
while (curr) {
cnt++
let [len, subCurr] = [0, curr]
// 计算 len
while (len < cnt && subCurr) {
len++
subCurr = subCurr.next
}
if (len & 1) { // len 为奇数就跳过
while (len-- > 0) {
curr = curr.next
prev = prev.next
}
} else { // len 为偶数
while (len-- > 1) { // 头插法
const next = curr.next
curr.next = next.next
next.next = prev.next
prev.next = next
}
prev = curr
curr = curr.next
}
}
return dummy.next
}时间复杂度：O(n)；空间复杂度：O(1)。