前言
见过不少算法里都涉及双指针，一个快指针，一个慢指针，有去判断中点的，有去判断环的。双指针解决环问题类似于一个追及问题：
《趣学算法》在一个环形跑道上，速度快的运动员从同一地点起跑，一个运动员速度快，另一个运动员速度慢。当两个人跑了一段时间后，速度快的运动员必然会再次追上并超过速度慢的运动员，原因很简单，因为跑道是环形的。
正文
节点数据结构
type TNode = { data: number, next: TNode | null, }
判断环函数签名
function is_cycle(node: TNode): boolean { let p1: TNode | null = node // 2. let p2: TNode | null = node while (p1 != null && p2 != null && p2.next != null) { //1. p1 = p1.next p2 = p2.next.next if (p1 === p2) { // 3. return true } } return false }
- 使用 typescript 时，需要特别注意这里p1 != null一定要补充上，虽然 while 循环里慢指针 p1 肯定不会在 p2 之前变成 null，但是 typescript 类型检查里通过不了，会提示 Type 'null' is not assignable to type 'TNode'.
- 因为 p1,p2 可能为 null，所以在申明类型时，需要声明成 TNode|null
- 这里就是快慢指针再次相遇的地方，即：相遇则有环，不相遇则无环。
查看结果
let node1: TNode = {data: 5, next: null} let node2: TNode = {data: 3, next: null} let node3: TNode = {data: 7, next: null} let node4: TNode = {data: 2, next: null} let node5: TNode = {data: 6, next: null} node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5 node5.next = node3 let result = is_cycle(node1) console.log("result -> ", result)
判断链表是否有环
附加
这块在练习的时候，被 typescript 的类型检查着实折腾了一番，但好记性不如烂笔头，还是挺有必要的。
