链表

相交链表

储存 headA 中的节点
如果 headB 中有相同节点，则是交点

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
    let set = new Set() // 记录 headA 中的节点
    while (headA) {
        set.add(headA)
        headA = headA.next
    }
 
    while (headB) {
        if (set.has(headB)) return headB // 交点
        headB = headB.next
    }
    return null
};

反转链表

把当前节点，指向前一个节点

function reverseList(head: ListNode | null): ListNode | null {
    let prev = null
    while (head) {
        let next = head.next // 保存下个节点
        head.next = prev // 修改指向
        prev = head
        head = next
    }
    return prev
};

合并有序链表

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    let head = new ListNode()
    let curr = head
    while (list1 && list2) { // 合并链表
        if (list1.val < list2.val) {
            curr.next = list1
            curr = curr.next
            list1 = list1.next
        } else {
            curr.next = list2
            curr = curr.next
            list2 = list2.next
        }
    }
    curr.next = list1 ?? list2 // 处理剩余节点
    return head.next
};

有序链表去重

对于节点 [a, b, c]，如果 a, b 相同，则 a -> c

function deleteDuplicates(head: ListNode | null): ListNode | null {
    let curr = head
    while (curr?.next) {
        if (curr.val === curr.next.val) { // 重复元素
            curr.next = curr.next.next
        } else {
            curr = curr.next
        }
    }
    return head
};

删除倒数节点

两个相距 n 的节点 a, b
当 b 走到终点时，a 刚好是倒数第 n 个节点

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    let dummy = new ListNode(0, head)
    let [a, b] = [dummy, dummy]
    for (let i = 0; i < n; i++) { // 初始化指针
        b = b.next
    }
 
    while (b?.next) {
        a = a.next
        b = b.next
    }
    a.next = a.next.next // 删除下一个节点
 
    return dummy.next
};

两两交换节点

对于节点 [a, b, c, d]，想要交换 b, c，只需要 a -> c, c -> b, b -> d

function swapPairs(head: ListNode | null): ListNode | null {
    let dummy = new ListNode(0, head)
    let curr = dummy
    while (curr?.next?.next) {
        let [a, b, c, d] = [curr, curr.next, curr.next.next, curr.next.next.next]
        a.next = c
        c.next = b
        b.next = d
        curr = b
    }
    return dummy.next
};

两数相加

节点的值等于 l1 + l2 + carry，其中 carry 表示进位

function addTwoNumbers(l1, l2) {
    let head = new ListNode()
    let curr = head
    let carry = 0
    while (l1 || l2) {
        let v1 = l1 ? l1.val : 0
        let v2 = l2 ? l2.val : 0
        let sum = v1 + v2 + carry
        let val = sum % 10
        carry = Math.floor(sum / 10)
        curr.next = new ListNode(val)
        curr = curr.next
        if(l1) l1 = l1.next
        if(l2) l2 = l2.next
    }
    if (carry) curr.next = new ListNode(1)
    return head.next
};

环形链表

如果节点已经访问过，则是环

function hasCycle(head: ListNode | null): boolean {
    let set = new Set()
    while (head) {
        if (set.has(head)) return true // 有环
        set.add(head)
        head = head.next
    }
    return false
};

环形链表 II

如果节点已经访问过，则是环入口

function detectCycle(head: ListNode | null): ListNode | null {
    let set = new Set()
    while (head) {
        if (set.has(head)) return head // 环入口
        set.add(head)
        head = head.next
    }
    return null
};

链表的中间结点

slow 走一步，fast 走两步
当 fast 走到终点时，slow 刚好走到一半

function middleNode(head: ListNode | null): ListNode | null {
    let [slow, fast] = [head, head]
    while (fast?.next) {
        slow = slow.next
        fast = fast.next.next
    }
    return slow
};