记录两道算法
反转链表
leetcode-cn.com/problems/re…
- 需求：以k个为一组，进行反转，如果k不是链表长度的倍数，最后凑不齐一组的保持不变。
- 考察的点是指针思想的应用。
- 拆分成几个小需求，最后整合。
- 首先，既然最后的一个或多个节点是不会反转的。所以每次执行反转前需要知道能不能凑齐k个。所以设计一个函数，参数是
node: 开始的节点和k: 多少个一组， 输出end: 结尾的节点，stop: 是否凑齐一组。
function findEnd(end, k) {
let i = 1
while (i !== k && end?.next !== null) {
// 当不足k个并且链表没有结束的时候
end = end.next
i++
}
// 如果 i !== k 的时候结束了上面的循环，意味着剩下的不足k个，凑不成一组
return [end, i !== k]
}
复制代码-
然后是反转数组，我们需要知道一组的开头和结尾，然后进行反转的操作
- 以三个反转为例（a -> b -> c -> d）
- 第一次反转 （a <- b, temp = c）,先用 temp 临时保存 c，然后反转 b 的指向，使其指向 a。
- 第二次反转 （a <- b <- c, temp = d),用temp2 临时保存 d， 然后反转 c 的指向，使其指向 b。
- ….
- 所以可以看到,最小颗粒的操作是用一个变量保存 a.next.next， 然后让 a.next 指向 a，代码如下：
const b = a.next const temp = b.next // c b.next = a 复制代码- 如果需要自动的反转数组，需要一个公共变量
temp, 需要一个变量指着 被反转(改变next)的节点。如果是上面的代码就是需要永远指着下一个 b。当 b 是结尾意味着这次反转的结束。所以设计一个函数， 参数是start: 开始的节点和end: 结尾的节点， start 不会等于 end。
function reverseGroup(n1, end) {
// 因为在 while 中 n1 会被改变为 n2(指针移动)， 所以不能在while中使用 n1.next
let n2 = n1.next
let n3
while(n1 !== end) {
n3 = n2.next // 保存被改变节点的原本指向
n2.next = n1 // 改变指向
// 移动指针
n1 = n2
n2 = n3
}
// 返回 n2 是希望将 可能存在的下一组开头保存起来返回出去，因为 end.next 的指向被改变了。
retun n2 // end.next
}
// 大概就是
a -> b -> c -> d -> e -> f -> g -> h 指针对位
1 2 3
a <- b -> c -> d -> e -> f -> g -> h 改变指向
1 2 3
a <- b -> c -> d -> e -> f -> g -> h 指针对位
1 2 3
a <- b <- c -> d -> e -> f -> g -> h 改变指向
1 2 3
...以此类推
a <- b <- c <- d <- e <- f <- g <- h -- ?
1 2
3
// while循环开头是更新 3 的位置，如果不走while循环，2 和 3 是同一个位置
// 1 == end 结束
复制代码-
反转了之后，头和尾需要重新定义链接。
-
比如
a -> b -> c -> d, 反转 bc 之后， a应该由 指向b 改成 指向c， b应该由 指向c 改成 指向d。即a -> c -> b -> d -
要求需要返回一个head，让链表完整表达，这个head是会根据反转改变一次，就是第一组反转的 end。
-
统计一下这时候我们有什么
function reverse(head, k) {
// 假如 k 是 1 的话，等于不用反转
if (k === 1) return head
let start = head,
lastStart // 上一组的start，即反转后的结尾
while (true) {
const [end, stop] = findEnd(start, k)
if (stop) return head
// 下面是确认凑齐一组， 不凑齐会直接return
if (head === start) {
// 反转第一组时是相等的
head = end
} else {
// 从第二组开始需要重新定义 start 和 end 反转后的指向
// 因为第二组开头会被第一组的start链接
// 总体反转是 start ··· end 变成 end ··· start
// 反转是一定成功的，所以可以提前修改 next 指向
lastStart.next = end
}
lastStart = start
// 这里是先让start对接下一组的开头
// 然后把start标记成新的开始
start = start.next = reverseGroup(start, end)
}
}
复制代码旋转链表
leetcode-cn.com/problems/ro…
旋转链表比上面的简单，不过在没找到规律之前挺晕的。
要求：
输入: 1 2 3 4 5 移动 2
输出：4 5 1 2 3
复制代码第一个直觉规律是，每次移动把最后一个节点的next指向第一个，然后斩断于倒数第二个的链接，然后重复n次，于是第一版代码出来了。
// 首先每次获取倒数第二个节点
let node = head
while(node.next.next) {
node = node.next
}
// 进行重新链接
cosnt last = node.next
last.next = head
node.next = null
head = last
//再套上一个for循环，执行n次
复制代码完整代码
function rotateRight(head, k) {
for(let i = 0; i < k; i++) {
let node = head
while(node.next.next) {
node = node.next
}
cosnt last = node.next
last.next = head
node.next = null
head = last
}
return head
}
复制代码结果是在 leetcode 上超过了 5% 的 JavaScript 版本的提交。真棒。
然后去看了一下题解，原来还有一个规律没注意到，就是当 n 是链表的长度的倍数的时候，链表是恢复原状的。所以链表实际要移动的是 n > length ? n % length : n
然后对应关系是 length - n, 即链表的第 length - n 个将会是链表的结尾， 第 length - n 个的 next，将是移动后的链表的开头。
所以问题是取得 第 length - n 个节点。
还有一个细节就是把链表的结尾和头部链接起来，让链表变成一个循环的链表。这样就只需要做掐断的动作。
function compute(node) {
// 获取链表的最后一个节点和链表的长度
let i = 1
while(node.next) {
node = node.next
i++
}
return [i, node]
}
function rotateRight(head, k) {
let [n, end] = compute(head)
end.next = head
k = k > n ? k % n : n
n = n - k
while(n--) {
end = end.next
}
head = end.next
end.next = null
return head
}
Copy the codeAnd then all of a sudden it went from 5% to 81%