Chapter 2 | 链表

链表是表示节点序列的数据结构。在单链表中，每个节点都指向链表中的下一个节点。双向链表为每个节点提供指向下一个节点和前一个节点的指针。

下图是一个双向链表：

Chapter 2 | 链表 - 图1
与数组不同，链表不提供对列表中特定 “index” 的固定时间访问。这意味着，如果你希望找到列表中的第 K 个元素，就需要遍历 K 个元素。

链表的好处是可以在固定的时间内从列表头添加和删除项。对于特定的应用程序，这可能很有用。

创建链表

下面的代码实现了一个非常基本的单链表。

  1. 1     class Node {
  2. 2         Node next= null;
  3. 3         int data; 
  4. 4
  5. 5         public Node(int d) {
  6. 6             data= d;
  7. 7         }
  8. 8
  9. 9         void appendToTail(int d) {
  10. 10             Node end= new Node(d);
  11. 11             Node n = this;
  12. 12             while (n.next != null) {
  13. 13                 n = n.next;
  14. 14             }
  15. 15             n.next = end;
  16. 16         }
  17. 17     }

在这个实现中，我们没有使用 LinkedList 数据结构。我们通过对链表头节点（head Node）的引用访问链表。以这种方式实现链表时，需要小心一点。如果多个对象需要引用链表，而链表的头节点发生了更改，该怎么办？一些对象可能仍然指向旧的头节点。

如果愿意，我们可以实现一个封装了 Node 类的 LinkedList 类。这实际上只有一个成员变量：head Node。这将在很大程度上解决前面所说的问题。

记住，当你在面试中讨论链表时，你必须清楚它是单链表还是双链表。

从单链表中删除节点

从链表中删除节点非常简单。给定一个节点 n，我们找到其前一节点 prev 并令 prev.next = n.next。如果实双向链表，我们还必须更新 n.next，令 n.next.prev = n.prev。 要记住的重要事项是（1）检查空指针和（2）根据需要更新头或尾指针。

此外，如果使用C、C++或其他需要开发人员进行内存管理的语言来实现此代码，则应考虑是否需要释放已删除的节点。

  1. 1     Node deleteNode(Node head, int d) {
  2. 2         Node n = head;
  3. 3
  4. 4         if (n.data == d) {
  5. 5             return head.next; /* moved head */
  6. 6         }
  7. 7
  8. 8         while (n.next != null) {
  9. 9             if (n.next.data == d) {
  10. 10                 n.next = n.next.next;
  11. 11                 return head; /* head didn't change */
  12. 12             }
  13. 13             n = n.next;
  14. 14         }
  15. 15         return head;
  16. 16     }

“Runner”技术

“runner”（或第二个指针）技术用于许多链表问题。runner 技术意味着你可以同时使用两个指针遍历链表，其中一个指针位于另一个指针之前。“快”节点可能领先固定的个数，或者它可能在“慢”节点遍历一个节点时跳过多个节点。

例如，假设你有一个链表 a1 -> a2 -> … -> an -> b1 -> b2 -> … -> bn，并且你想把它重新排列成 a1 -> b1 -> a2 -> b2 -> … -> an -> bn。你不知道链表的长度（但是你知道长度是偶数）。

你可以使用一个指针 p1​（快指针），在 ​p2​ 每移动一个元素时 ​p1​ 移动两个元素。当 ​p1 到达链表的末尾时，p2 将位于中点。然后，将 p1 移回到链表头并开始“织入（weaving）”元素。在每次迭代中，p2 选择一个元素并将其插入 p1​ 之后。

递归问题

许多链表问题依赖于递归。如果在解决链表问题时遇到困难，应该研究递归方法是否可行。这里我们不深入讨论递归，因为后面的一章将专门讨论它。

但是，你应该记住递归算法至少占用 O(n)​ 空间，其中 n 是递归调用的深度。所有递归算法都可以替换成使用迭代实现，尽管它们可能要复杂得多。

Interview Questions

  • 2.1 删除重复项（Remove Dups）：编写代码从未排序的链表中删除重复项。

    FOLLOW UP

    如果不允许使用临时缓冲区，如何解决这个问题?

    提示：#9, #40

  • 2.2 返回第 K 到最后（Return Kth to Last）：实现一个算法，以找到单链表的第 K 个到最后一个元素。

    提示：#8, #25, #41, #67, #126

  • 2.3 删除中间节点（Delete Middle Node）：实现一个算法，以删除单链表的中间节点（即，除了第一个和最后一个节点以外的任何节点，不一定是确切的中间节点），要求仅允许访问该节点。

    EXAMPLE

    1. Input: the node c from the linked list a->b->c->d->e->f
    2. Result: nothing is returned, but the new linked list looks like a->b->d->e->f

    提示：#72

  • 2.4 分区（Partition）：编写代码以围绕值 x 对链表进行分区，使所有小于 x 的节点排在所有大于或等于 x 的节点之前。 如果 x 包含在列表中，则 x 的值仅需在小于 x 的元素之后（请参见下文）。 分区元素 x 可以出现在“右分区”中的任何位置； 不需要将它放在左右分区之间。

    EXAMPLE

    1. Input: 3 -> 5 -> 8 -> 5 -> 10 -> 2 -> 1 [partition= 5]
    2. Output: 3 -> 1 -> 2 -> 10 -> 5 -> 5 -> 8

    提示：#3, #24

  • 2.5 总和列表（Sum Lists）：你有两个由链表表示的数字，其中每个节点都包含一个数字。 这些数字以相反的顺序存储，即第一位的数字就位于列表的开头。编写一个函数，将两个数字相加，然后将和以链表的形式返回。

    EXAMPLE

    1. Input: (7-> 1 -> 6) + (5 -> 9 -> 2). That is, 617 + 295.
    2. Output: 2 -> 1 -> 9. That is, 912.

    FOLLOW UP

    假设数字以正序存储。重复上述问题。

    EXAMPLE

    1. Input: (6 -> 1 -> 7) + (2 -> 9 -> 5). That is, 617 + 295.
    2. Output: 9 -> 1 -> 2. That is, 912.

    提示：#7, #30, #71, #95, #109

  • 2.6 回文（Palindrome）：实现一个函数来检查一个链表是否是一个回文。

    提示：#5, #13, #29, #61, #101

  • 2.7 相交（Intersection）：给定两个（单）链表，判断两个链表是否相交。是的话返回相交节点。请注意，相交是基于引用而不是基于值定义的。也就是说，如果第一个链表的第 k 个节点与第二个链表的第 j 个节点完全相同（引用层面上），那么它们相交。

    提示：#20, #45, #55, #65, #76, #93, #111, #120, #129

  • 2.8 循环检测（Loop Detection）：给定一个循环链表，实现一个算法，返回循环开始处的节点。

    DEFINITION

    循环链表：一种（不纯的）链表，其中一个节点的下一个指针指向较早的节点，从而在链表中形成一个循环。

    EXAMPLE

    1. Input: A -> B -> C -> D -> E -> C [the same C as earlier]
    2. Output: C

    提示：#50, #69, #83, #90

附加问题：树和图(#4.3)，面向对象设计(#7.12)，系统设计和可扩展性(#9.5)，中等问题(#16.25)，困难问题(#17.12)。

提示从第 653 页开始。