You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
只反转链表
在找到需要反转的链表,用 1 去反转
每一轮循环中,将链表视为
pre => start => *** => end => next
我们翻转 start => *** => end 这一段, 变为
pre end => *** => start next
再将原链表和翻转后的合并即可,然后寻找下一段要反转的链表继续循环
pre => end => *** => start => next
// 定义链表节点
class Node {
constructor(v, last) {
this.next = null
this.value = v
if (last) {
last.next = this
}
}
}
let head = makeList(10)
console.info(toString(head))
head = invert(head, 3)
console.info(toString(head))
// 原链表: 0,1,2,3,4,5,6,7,8,9
// 反转后: 2,1,0,5,4,3,8,7,6,9
// ---- 核心思想 -----
/**
* 链表每m个节点反转
* @param {*} head
* @param {*} n
*/
function invert(head, n) {
let pre = new Node(999, null)
pre.next = head
let start = head
let end = head
// 缓存头
head = pre
let count = 1
while (start && end) {
// 查找需要反转的链表 end 节点
if (count < n) {
count++
end = end.next
} else {
count = 1
// 缓存对 end 之后的链表的索引
let next = end.next
// 反转 start -> ** -> end 这段链表
revert(start, next)
// 反转成功后, end 节点是新链表的头了, 而 start 是尾了
pre.next = end
// 反转的链表连上剩下的链表
start.next = next
// 初始化下一段要反转的链表段
pre = start
start = next
end = next
}
}
return head.next
}
/**
* 给定一个链表头和结束标记进行反转
* @param {*} start
* @param {*} endTag
*/
function revert(start, endTag) {
let temp
let pre = null
while (start !== endTag) {
temp = start.next
start.next = pre
pre = start
start = temp
}
return pre
}
// ----工具-----
// 构造一个链表
function makeList(length) {
const head = new Node(-1, null)
Array.from({length}, (_, i) => i).reduce((last, key) => new Node(key, last), head)
return head.next
}
// 打印链表
function toString(head) {
let temp = new Node(999, null)
temp.next = head
let show = []
while ((temp = temp.next)) {
show.push(temp.value)
}
return show.join(',')
}
No description provided.
The text was updated successfully, but these errors were encountered: