0_双指针链表.md

双指针链表

https://labuladong.gitee.io/algo/1/4/

合并两个有序链表

力扣第 21 题「合并两个有序链表」

https://leetcode-cn.com/problems/merge-two-sorted-lists/

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {

};

我们的 while 循环每次比较 p1 和 p2 的大小，把较小的节点接到结果链表上，看如下 GIF：

形象地理解，这个算法的逻辑类似于拉拉链，l1, l2 类似于拉链两侧的锯齿，指针 p 就好像拉链的拉索，将两个有序链表合并；或者说这个过程像蛋白酶合成蛋白质，l1, l2 就好比两条氨基酸，而指针 p 就好像蛋白酶，将氨基酸组合成蛋白质。

**代码中还用到一个链表的算法题中是很常见的「虚拟头结点」技巧，也就是 dummy 节点。**你可以试试，如果不使用 dummy 虚拟节点，代码会复杂很多，而有了 dummy 节点这个占位符，可以避免处理空指针的情况，降低代码的复杂性。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    const res = new ListNode(0, null)
    let p = res
    let p1 = list1, p2 = list2
    while (p1 && p2) {
        if (p1.val > p2.val) {
            p.next = p2
            p2 = p2.next
        } else {
            p.next = p1
            p1 = p1.next
        }
        p = p.next
    }
    if (p1) {
        p.next = p1
    }
    if (p2) {
        p.next = p2
    }
    return res.next
};

合并 k 个有序链表

力扣第 23 题「合并K个升序链表」

https://leetcode-cn.com/problems/merge-k-sorted-lists/

合并 k 个有序链表的逻辑类似合并两个有序链表，难点在于，如何快速得到 k 个节点中的最小节点，接到结果链表上？

这里我们就要用到 优先级队列（二叉堆） 这种数据结构，把链表节点放入一个最小堆，就可以每次获得 k 个节点中的最小节点：

优先队列 pq 中的元素个数最多是 k，所以一次 poll 或者 add 方法的时间复杂度是 O(logk)；所有的链表节点都会被加入和弹出 pq，所以算法整体的时间复杂度是 O(Nlogk)，其中 k 是链表的条数，N 是这些链表的节点总数。

class Heap {
    arr: any[]
    compare: (a: any, b: any) => boolean
    constructor(compare) {
        this.arr = [0]; // 下标从1开始好算，下标0废弃
        this.compare = (typeof compare === 'function') ? compare : this._defaultCompare;
    }

    /**
     * 根据可迭代对象生成堆
     * @param {*} data iterable 对象
     * @param {*} compare
     */
    static heapify(data, compare = undefined) {
        const heap = new Heap(compare);
        for (const item of data) {
            heap.push(item);
        }
        return heap;
    }

    push(item) {
        const { arr } = this;
        arr.push(item);
        this._up(arr.length - 1);
        // console.log('push', item, arr.slice(1));
    }

    pop() {
        if (this.size === 0) return null; //行为同Java的PriorityQueue
        const { arr } = this;
        this._swap(1, arr.length - 1);// 末尾的换上来，堆顶放到最后等待返回
        const res = arr.pop();
        this._down(1);// 换上来的末尾尝试下沉
        return res;
    }

    /**
     * 堆中元素数量
     */
    get size() {
        return this.arr.length - 1;
    }

    /**
     * 返回堆顶元素
     */
    peek() {
        return this.arr[1];
    }

    /**
     * 上浮第k个元素
     * @param {int} k
     */
    _up(k) {
        const { arr, compare, _parent } = this;
        // k 比它的父节点更靠近堆顶，应该继续上浮（k=1 表示已经到达堆顶）
        while (k > 1 && compare(arr[k], arr[_parent(k)])) {
            this._swap(_parent(k), k);
            k = _parent(k);
        }
    }

    /**
     * 下沉第k个元素
     * @param {int} k
     */
    _down(k) {
        const { arr, compare, _left, _right, size } = this;
        // 如果沉到堆底，就沉不下去了
        while (_left(k) <= size) {
            let child = _left(k);
            if (_right(k) <= size && compare(arr[_right(k)], arr[child])) {
                child = _right(k); // 选择左右子节点中更靠近堆顶的，这样能维持下沉后原本的 left与right 之间的顺序关系
            }
            // 如果当前的k比子节点更靠近堆顶，不用下沉了
            if (compare(arr[k], arr[child])) return;
            // 下沉
            this._swap(k, child);
            k = child;
        }
    }

    _left(k) { return k * 2; }
    _right(k) { return k * 2 + 1; }
    _parent(k) { return Math.floor(k / 2); }

    /**
     * 交换位置
     * @param {int} i
     * @param {int} j
     */
    _swap(i, j) {
        const arr = this.arr;
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }

    /**
     * a是否比b更接近堆顶，默认为小顶堆
     * @param {*} a
     * @param {*} b
     * @return {boolean}
     */
    _defaultCompare(a, b) {
        return a < b;
    }
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
if (!lists || !lists.length) { return null }

    // 虚拟头节点
    const dummy = new ListNode(0, null)
    let p = dummy

    // 优先级队列，最小堆 PriorityQueue
    const pg = new Heap((a, b) => a.val < b.val)
    for (const i of lists) {
        if (i) {
            pg.push(i)
        }
    }

    while (pg.size) {
        // 获取最小节点，接到结果链表中
        const node = pg.pop()
        p.next = node
        if (node.next) {
            pg.push(node.next)
        }
        p = p.next
    }
    return dummy.next
};

单链表的分解

力扣第 86 题「分隔链表」

https://leetcode.cn/problems/partition-list/

我们可以把原链表分成两个小链表，一个链表中的元素大小都小于 x，另一个链表中的元素都大于等于 x，最后再把这两条链表接到一起，就得到了题目想要的结果。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function partition(head: ListNode | null, x: number): ListNode | null {
    const dummy1 = new ListNode()
    const dummy2 = new ListNode()
    let p1 = dummy1, p2 = dummy2, p = head
    while (p) {
        if (p.val >= x) {
            p2.next = p
            p2 = p2.next
        } else {
            p1.next = p
            p1 = p1.next
        }
        // // 断开原链表中的每个节点的 next 指针
        const temp = p.next
        p.next = null
        p = temp
    }
    p1.next = dummy2.next

    return dummy1.next
};

单链表的倒数第-k-个节点

力扣第 19 题「删除链表的倒数第 N 个结点」

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

一个 ListNode 头结点代表一条单链表，你不能直接得出这条链表的长度 l，而需要先遍历一遍链表算出 l 的值，然后再遍历链表计算第 l - n + 1 个节点。这个解法需要遍历两次链表才能得到出倒数第 k 个节点。

如果用 big O 表示法来计算时间复杂度，无论遍历一次链表和遍历两次链表的时间复杂度都是 O(N)，但遍历一遍更有技巧性

首先，我们先让一个指针 p1 指向链表的头节点 head，然后走 n 步 趁这个时候，再用一个指针 p2 指向链表头节点 head 等 p1 走到 null， p2则恰好停链表的倒数第 N 个节点上

使用虚拟头结点的技巧是为了防止出现空指针的情况，比如说链表总共有 5 个节点，题目就让你删除倒数第 5 个节点，也就是第一个节点，那按照算法逻辑，应该首先找到倒数第 6 个节点。但第一个节点前面已经没有节点了，这就会出错。 但有了我们虚拟节点 dummy 的存在，就避免了这个问题，能够对这种情况进行正确的删除。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    const dummy = new ListNode()
    dummy.next = head
    const x = findFromEnd(dummy, n + 1)
    x.next = x.next.next
    return dummy.next
};

function findFromEnd(head: ListNode | null, n: number) {
    let p1 = head
    for (let i = 0; i < n; i++) {
        p1 = p1.next
    }
    let p2 = head
    while (p1) {
        p2 = p2.next
        p1 = p1.next
    }
    return p2
}

单链表的中点

力扣第 876 题「链表的中间结点」

https://leetcode.cn/problems/middle-of-the-linked-list/

问题的关键也在于我们无法直接得到单链表的长度 n，常规方法也是先遍历链表计算 n，再遍历一次得到第 n / 2 个节点，也就是中间节点。

如果想一次遍历就得到中间节点，也需要耍点小聪明，使用「快慢指针」的技巧： 我们让两个指针 slow 和 fast 分别指向链表头结点 head。 每当慢指针 slow 前进一步，快指针 fast 就前进两步，这样，当 fast 走到链表末尾时，slow 就指向了链表中点。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

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

链表中环的入口节点

https://leetcode.cn/problems/c32eOV/

当快慢指针相遇时，让其中任一个指针指向头节点，然后让它俩以相同速度前进，再次相遇时所在的节点位置就是环开始的位置。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function detectCycle(head: ListNode | null): ListNode | null {
    let fast = head, slow = head
    while (fast && fast.next) {
        fast = fast.next.next
        slow = slow.next
        if (fast === slow) { break }
    }
    if (!fast || !fast.next) {
        // fast 遇到空指针说明没有环
        return null
    }
    // 重新指向头结点
    slow = head
    // 快慢指针同步前进，相交点就是环起点
    while (slow !== fast) {
        fast = fast.next
        slow = slow.next
    }
    return slow
};

两个链表是否相交

力扣第 160 题「相交链表」

https://leetcode.cn/problems/intersection-of-two-linked-lists/

如果把两条链表首尾相连，那么「寻找两条链表的交点」的问题转换成了前面讲的「寻找环起点」的问题：

把题目输入的链表转化成环形链表求解之后记得还要改回来

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function getIntersectionNode(headA: ListNode | null, headB: ListNode | null): ListNode | null {
    if (!headA || !headB) { return null }
    let p1 = headA
    while (p1 && p1.next) {
        p1 = p1.next
    }
    // 连接headA与headB 转化成寻找环形链表
    p1.next = headB
    const head = headA
    let fast = head, slow = head
    while (fast && fast.next) {
        fast = fast.next.next
        slow = slow.next
        if (fast === slow) { break }
    }
    if (!fast || !fast.next) {
        // 还原headA尾节点
        p1.next = null
        // fast 遇到空指针说明没有环
        return null
    }
    // 重新指向头结点
    slow = head
    // 快慢指针同步前进，相交点就是环起点
    while (slow !== fast) {
        fast = fast.next
        slow = slow.next
    }
    // 还原headA尾节点
    p1.next = null
    return slow
};