链表

class ANode {
    constructor(public value: number, public next?: ANode) { }
}

// printNodes(revNodes(makeNodes([1, 2, 3, 4], 0)!))
// printNodes(revNodes(makeNodes([1], 0)!))
// printNodes(revNodes(revNodes(makeNodes([1, 2, 3, 4], 0)!)))

let loopH = new ANode(2, undefined)
let loopN = new ANode(3, loopH);
loopH.next = loopN;

hasCircleNode(new ANode(1, loopH));
console.log('circle node:', findCircleNode(new ANode(1, loopH)));

function makeNodes(values: number[], index: number): ANode | undefined {
    if (index >= values.length) {
        return undefined;
    } else {
        return new ANode(values[index], makeNodes(values, index + 1))
    }
}

function printNodes(n: ANode) {
    let cur: ANode | undefined = n;
    let max = 5;
    while (cur != undefined && (max--) > 0) {
        console.log(cur.value)
        cur = cur.next;
    }
}

function revNodes(n: ANode): ANode {
    let cur = n;
    let prev: ANode | undefined = undefined;
    let next: ANode | undefined = cur.next;
    while (next != undefined) {
        cur.next = prev;
        prev = cur;
        cur = next;
        next = cur.next;
    }
    cur.next = prev;
    return cur;
}

function hasCircleNode(n: ANode): boolean {
    let revN = revNodes(n);
    let c: ANode | undefined = n;
    let c2: ANode | undefined = revN;
    if (c != c2) {
        console.log("no loop node.")
        return false;
    }
    console.log("has circle node.")
    return true;
}

function findCircleNode(n: ANode): ANode | undefined {
    let c = n;
    let markNode = new ANode(-1)
    while (c.next != undefined) {

        if (c.next == markNode) return c;
        let next = c.next;
        c.next = markNode;
        c= next;
    }
    return undefined;
}