双指针专题算法：替换数字、链表相交、环形链表ii

1. 不用申请新数组。
2. 从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

1. 使用readline模块从标准输入中读取用户输入并显示输出到标准输出。
2. 利用charCodeAt()方法判断字符是字母还是数字。
3. 监听输入行，遍历原数组以确定扩容后新数组的长度。
4. 创建新数组，从后往前填充操作。

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;}}// 如果没有环，返回 nullif (!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;
};