单链表

单链表中的每个结点不仅包含值，还包含链接到下一个结点的引用字段。通过这种方式，单链表将所有结点按顺序组织起来。

下面是一个单链表的例子：
singleLinkedList.png

与数组不同，我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素，我们必须从头结点逐个遍历。 我们按索引来访问元素平均要花费 O(N) 时间，其中 N 是链表的长度。

添加节点

如果我们想在给定的结点 prev 之后添加新值，我们应该：

  1. 使用给定值初始化新结点 cur
    singleLinkedListAdd1.png
  2. 将 cur 的 next 字段链接到 prev 的下一个结点 next ；
    singleLinkedListAdd2.png
  3. 将 prev 中的 next 字段链接到 cur。
    singleLinkedListAdd3.png

我们使用头结点来代表整个列表。因此，在列表开头添加新节点时更新头结点 head 至关重要。
在开头添加结点，我们应该：

  1. 初始化一个新结点 cur ；
  2. 将新结点链接到我们的原始头结点 head。
  3. 将 cur 指定为 head 。

删除节点

如果我们想从单链表中删除现有结点 cur，可以分两步完成：

  1. 找到 cur 的上一个结点 prev 及其下一个结点 next ；
    singleLinkedListDelete1.png
  2. 接下来链接 prev 到 cur 的下一个节点 next 。
    singleLinkedListDelete2.png

在我们的第一步中，我们需要找出 prev 和 next。使用 cur 的参考字段很容易找出 next，但是，我们必须从头结点遍历链表，以找出 prev，它的平均时间是 O(N)，其中 N 是链表的长度。因此，删除结点的时间复杂度将是 O(N)。
空间复杂度为 O(1)，因为我们只需要常量空间来存储指针。

如果想要删除第一个结点，我们可以简单地将下一个结点分配给 head。

链表中的双指针问题

给定一个链表，判断链表中是否有环。

想象一下，有两个速度不同的跑步者。如果他们在直路上行驶，快跑者将首先到达目的地。但是，如果它们在圆形跑道上跑步，那么快跑者如果继续跑步就会追上慢跑者。

这正是我们在链表中使用两个速度不同的指针时会遇到的情况：

  • 如果没有环，快指针将停在链表的末尾。
  • 如果有环，快指针最终将与慢指针相遇。

这两个指针的适当速度应该是多少？

一个安全的选择是每次移动慢指针一步，而移动快指针两步。每一次迭代，快速指针将额外移动一步。如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针。

用于解决链表中的双指针问题的模板：

// Initialize slow & fast pointers
ListNode slow = head;
ListNode fast = head;
/**
 * Change this condition to fit specific problem.
 * Attention: remember to avoid null-pointer error
 **/
while (slow != null && fast != null && fast.next != null) {
    slow = slow.next;           // move slow pointer one step each time
    fast = fast.next.next;      // move fast pointer two steps each time
    if (slow == fast) {         // change this condition to fit specific problem
        return true;
    }
}
return false;   // change return value to fit specific problem
  1. 在调用 next 字段之前，始终检查节点是否为空。
    获取空节点的下一个节点将导致空指针错误。例如，在我们运行 fast = fast.next.next 之前，需要检查 fast 和 fast.next 不为空。
  2. 仔细定义循环的结束条件。

复杂度分析

空间复杂度分析容易。如果只使用指针，而不使用任何其他额外的空间，那么空间复杂度将是 O(1)。但是，时间复杂度的分析比较困难。为了得到答案，我们需要分析运行循环的次数。

在前面的查找循环示例中，假设我们每次移动较快的指针 2 步，每次移动较慢的指针 1 步。

  • 如果没有循环，快指针需要 N/2 次才能到达链表的末尾，其中 N 是链表的长度。
  • 如果存在循环，则快指针需要 M 次才能赶上慢指针，其中 M 是列表中循环的长度。

显然，M <= N 。所以我们将循环运行 N 次。对于每次循环，我们只需要常量级的时间。因此，该算法的时间复杂度总共为 O(N)。

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。
circularlinkedlist.png

示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。
circularlinkedlist_test2.png

示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。
circularlinkedlist_test3.png

提示：

链表中节点的数目范围在范围 [0, 104] 内
-105 <= Node.val <= 105
pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

算法：

我们使用两个指针，fast 与 slow。它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。

如下图所示，设链表中环外部分的长度为 a。slow 指针进入环后，又走了 b 的距离与 fast 相遇。此时，fast 指针已经走完了环的 n 圈，因此它走过的总距离为 a+n(b+c)+b=a+(n+1)b+nc。

根据题意，任意时刻，fast 指针走过的距离都为 slow 指针的 22 倍。因此，我们有
a+(n+1)b+nc=2(a+b)⟹a=c+(n−1)(b+c)

有了 a=c+(n-1)(b+c) 的等量关系，我们会发现：从相遇点到入环点的距离加上 n−1 圈的环长，恰好等于从链表头部到入环点的距离。

因此，当发现 slow 与 fast 相遇时，我们再额外使用一个指针 ptr。起始，它指向链表头部；随后，它和 slow 每次向后移动一个位置。最终，它们会在入环点相遇。

142_fig1.png

代码：

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (slow != null && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

复杂度分析：

  • 时间复杂度：O(N)，其中 N 为链表中节点的数目。在最初判断快慢指针是否相遇时，slow 指针走过的距离不会超过链表的总长度；随后寻找入环点时，走过的距离也不会超过链表的总长度。因此，总的执行时间为O(N)+O(N)=O(N)。
  • 空间复杂度：O(1)。我们只使用了slow,fast,ptr 三个指针。

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

remove_ex1.jpg

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

算法：

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

具体地，初始时 first 和 second 均指向头节点。我们首先使用 first 对链表进行遍历，遍历的次数为 n。此时，first 和 second 之间间隔了 n−1 个节点，即 first 比 second 超前了 n 个节点。

在这之后，我们同时使用 first 和 second 对链表进行遍历。当 first 遍历到链表的末尾（即 first 为空指针）时，second 恰好指向倒数第 n 个节点。

如果我们能够得到的是倒数第 n 个节点的前驱节点而不是倒数第 n 个节点的话，删除操作会更加方便。因此我们可以考虑在初始时将 second 指向哑节点，其余的操作步骤不变。这样一来，当 first 遍历到链表的末尾时，second 的下一个节点就是我们需要删除的节点。

代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = head;
        ListNode second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first.next;
        }
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        ListNode ans = dummy.next;
        return ans;
    }
}

复杂度分析：

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

206. 反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：
rev1ex1.jpg

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：
rev1ex2.jpg

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

算法：

首先我们建立一个 dummy 节点，并将 dummy 的 next 指向 head 。每次循环将 head 节点的下一个节点放到 dummy 节点之后，直到 head 到最后一个节点。

代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head==null){
            return null;
        }
        
        ListNode dummy = new ListNode(0,head);

        while (head.next!=null){
            ListNode temp2 = head.next;
            ListNode temp3 = dummy.next;
            dummy.next = temp2;
            head.next = temp2.next;
            temp2.next = temp3;
        }
        return dummy.next;
    }
}

复杂度分析：

  • 时间复杂度：在该算法中，每个结点只移动一次。因此，时间复杂度为 O(N)，其中 N 是链表的长度。
  • 空间复杂度： 我们只使用常量级的额外空间，所以空间复杂度为 O(1)。

双链表

双链接列表中的结点具有 Value 字段，用于顺序链接结点的 Next 引用字段，还有指向前一个节点的 Prev 引用字段。

DoubleLinkedList.png

添加节点

如果我们想在现有的结点 prev 之后插入一个新的结点 cur，我们可以将此过程分为两个步骤：

  1. 链接 cur 与 prev 和 next，其中 next 是 prev 原始的下一个节点；
    DoubleLinkedListAdd1.png
  2. 用 cur 重新链接 prev 和 next。
    DoubleLinkedListAdd2.png
    与单链表类似，添加操作的时间和空间复杂度都是 O(1)。

删除节点

如果我们想从双链表中删除一个现有的结点 cur，我们可以简单地将它的前一个结点 prev 与下一个结点 next 链接起来。
DoubleLinkedListDelete.png

小结

单链表和双链表它们在许多操作中是相似的。

  1. 它们都无法在常量时间内随机访问数据。
  2. 它们都能够在 O(1) 时间内在给定结点之后或列表开头添加一个新结点。
  3. 它们都能够在 O(1) 时间内删除第一个结点。

但是删除给定结点(包括最后一个结点)时略有不同。

  • 在单链表中，它无法获取给定结点的前一个结点，因此在删除给定结点之前我们必须花费 O(N) 时间来找出前一结点。
  • 在双链表中，这会更容易，因为我们可以使用“prev”引用字段获取前一个结点。因此我们可以在 O(1) 时间内删除给定结点。

compare.png

如果你需要经常添加或删除结点，链表可能是一个不错的选择。

如果你需要经常按索引访问元素，数组可能是比链表更好的选择。

最后修改：2022 年 12 月 20 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏