双指针专题算法：替换数字、链表相交、环形链表ii
3.替换数字
思路
- 不用申请新数组。
- 从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。
步骤
- 使用readline模块从标准输入中读取用户输入并显示输出到标准输出。
- 利用charCodeAt()方法判断字符是字母还是数字。
- 监听输入行，遍历原数组以确定扩容后新数组的长度。
- 创建新数组，从后往前填充操作。
部分代码解释
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
})提交代码
// 从标准输入中读取输入行并将输出显示未标准输出
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
})
// 利用charAtCode()判断是字母或数字
function main() {
// 获取数字和字母的ASCII码表示范围
const num0 = "0".charCodeAt();
const num9 = "9".charCodeAt();
const a = "a".charCodeAt();
const z = "z".charCodeAt();
// 进行判断
function isNumber(val) {
return val >= num0 && val <= num9;
}
function isAZ(val) {
return val >= a && val <= z;
}
// 新数组扩容的记录
let n = 0;
// 监听每一行, 确定扩容后新数组的长度
rl.on("line", (input)=>{
for(let i = 0; i < input.length; i++) {
const val = input[i].charCodeAt();
if(isAZ(val)) {
n++;
}
if(isNumber(val)) {
n += 6;
}
}
// 创建新数组,从后往前进行填充
const ans = new Array(n).fill(0);
let index = input.length - 1; // 原数组的最后一个位置
for(let i = n - 1; i >= 0; i--) {
const val = input[index].charCodeAt();
if(isAZ(val)){
ans[i] = input[index];
}
if(isNumber(val)) {
ans[i] = "r";
ans[i - 1] = "e";
ans[i - 2] = "b";
ans[i - 3] = "m";
ans[i - 4] = "u";
ans[i - 5] = "n";
i -= 5;
}
index --;
}
console.log(ans.join(""));
})
}
main();题目
链接
[链表成环ii](https://leetcode.cn/submissions/detail/593083820/)
方法
1. 判断是否存在环：
- 使用快慢指针：
- 快指针每次走两步。
- 慢指针每次走一步。
- 如果链表中存在环，快慢指针一定会在环中相遇。
- 如果链表没有环，快指针会率先到达链表末尾。
2. 找到环的起点：
- 假设从链表头到环起点的距离为 a，环起点到相遇点的距离为 b，环的长度为 L。
- 当快慢指针相遇时，快指针走的总步数是慢指针的两倍，且有：2×(a+b)=a+b+n×L，化简得：a=n×L−b，说明从链表头到环起点的距离 a 等于从相遇点沿环走 n×L−b 的距离。
- 因此，当两个指针分别从链表头和相遇点出发，每次走一步，它们会在环的起点相遇。
实现
时间复杂度：O(n)，其中 n 是链表的节点数。快慢指针相遇前，指针走的次数小于链表长度，快慢指针相遇后，两个指针走的次数也小于链表长度，总体为走的次数小于 2n
var detectCycle = function(head) {
if (!head || !head.next) return null;
let slow = head;
let fast = head;
let hasCycle = false;
// 判断是否存在环
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
hasCycle = true;
break;
}
}
// 如果没有环，返回 null
if (!hasCycle) return null;
// 找到环的起点
let entry = head;
while (entry !== slow) {
entry = entry.next;
slow = slow.next;
}
return entry; // 返回环的起点
};
题目
[142.链表相交](https://leetcode.cn/submissions/detail/593083820/)
# 解题思路
方法
要找出两个链表相交节点的指针，
用双指针方法，让链表A（较长的一方链表）尾部与链表B对齐，然后遍历比较是否curA == curB，若相等，返回的值即为交点指针
实现
如何让链表A 与 链表B 尾部对齐？
双指针法
1. **计算两个链表的长度**：首先遍历两个链表，计算它们的长度 `lenA` 和 `lenB`。
2. **对齐两个链表的尾部**：将较长的链表的指针向前移动 `|lenA - lenB|` 步，这样两个链表的尾部就对齐了。
3. **同时遍历两个链表**：从对齐的位置开始，同时遍历两个链表，比较节点是否相同。如果找到相同的节点，返回该节点；如果遍历完都没有找到相同的节点，返回 `null`。
### AC代码
var getIntersectionNode = function(headA, headB) {
if (!headA || !headB) return null;
let lenA = 0, lenB = 0;
let curA = headA, curB = headB;
// 计算两个链表的长度
while (curA) {
lenA++;
curA = curA.next;
}
while (curB) {
lenB++;
curB = curB.next;
}
// 重置指针
curA = headA;
curB = headB;
// 对齐两个链表的尾部
if (lenA > lenB) {
for (let i = 0; i < lenA - lenB; i++) {
curA = curA.next;
}
} else {
for (let i = 0; i < lenB - lenA; i++) {
curB = curB.next;
}
}
// 同时遍历两个链表，比较节点是否相同
while (curA && curB) {
if (curA === curB) {
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
};