情深缘浅√ 2022-05-04 06:51:33
楼上的各位,这题用数组做就没意思了啊
纯链表加索引解决的思路:
拆分为2个函数
- 只反转链表
- 在找到需要反转的链表,用 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(',') }
- 共 1 页
- 1
const NOT_INCLUDE = -1;
String.prototype.indexOf = function(string, start = 0) {
if(typeof this !== 'string') throw new SyntaxError('SyntaxError, needs a string');
const reg = new RegExp(
${string}
, 'ig');reg.lastIndex = start;
const result = reg.exec(this);
return result?.index ?? NOT_INCLUDE;
}
Array.prototype.indexOf = function(item, start = 0) {
if(!item) return NOT_INCLUDE;
if(Array.isArray(this)) throw new SyntaxError('syntax error, needs an array!');
for (let i = start; i < this.length; i++)
}
第 151 题:用最简洁代码实现 indexOf 方法?