链表(Java版)

链表(Java版)

在链表操作中，我们通常通过生成一个 dummy 哑节点，来避免空链表的判断。

19.删除链表的倒数第 N 个结点

方法一：计算链表长度

为了方便删除操作，我们可以从哑节点开始遍历 L−n+1 个节点。当遍历到第 L−n+1 个节点时，它的下一个节点就是我们需要删除的节点，这样我们只需要修改一次指针，就能完成删除操作。

方法三：双指针

我们可以使用两个指针 first 和 second 同时对链表进行遍历，并且 first 比 second 超前 n 个节点。当 first 遍历到链表的末尾时，second 就恰好处于倒数第 n 个节点。

时间复杂度：O(L)，其中 L 是链表的长度。
空间复杂度：O(1)。

21.合并两个有序链表

1. 当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里。
2. 当 l1 和 l2 有一个是空的,只需要简单地将非空链表接在合并链表的后面。

23.合并K个升序链表

方法一：顺序合并

已经有合并两个有序链表的前提，直接遍历数组，依次合并两个链表得到结果。

方法二：分治合并

将 k 个链表分组并将同一组中的链表合并（递归实现）

进时间复杂度为 O(kn×logk)
空间复杂度,递归会使用到 O(logk) 空间代价的栈空间