链表是表示节点序列的数据结构。在单链表中，每个节点都指向链表中的下一个节点。双向链表为每个节点提供指向下一个节点和前一个节点的指针。
下图是一个双向链表：
链表的好处是可以在固定的时间内从列表头添加和删除项。对于特定的应用程序，这可能很有用。
下面的代码实现了一个非常基本的单链表。
1 class Node {
2 Node next= null;
3 int data;
4
5 public Node(int d) {
6 data= d;
7 }
8
9 void appendToTail(int d) {
10 Node end= new Node(d);
11 Node n = this;
12 while (n.next != null) {
13 n = n.next;
14 }
15 n.next = end;
16 }
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 Node deleteNode(Node head, int d) {
2 Node n = head;
3
4 if (n.data == d) {
5 return head.next; /* moved head */
6 }
7
8 while (n.next != null) {
9 if (n.next.data == d) {
10 n.next = n.next.next;
11 return head; /* head didn't change */
12 }
13 n = n.next;
14 }
15 return head;
16 }“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 是递归调用的深度。所有递归算法都可以替换成使用迭代实现，尽管它们可能要复杂得多。
-
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
Input: the node c from the linked list a->b->c->d->e->f 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
Input: 3 -> 5 -> 8 -> 5 -> 10 -> 2 -> 1 [partition= 5] Output: 3 -> 1 -> 2 -> 10 -> 5 -> 5 -> 8提示：#3, #24
-
2.5 总和列表（Sum Lists）：你有两个由链表表示的数字，其中每个节点都包含一个数字。 这些数字以相反的顺序存储，即第一位的数字就位于列表的开头。编写一个函数，将两个数字相加，然后将和以链表的形式返回。
EXAMPLE
Input: (7-> 1 -> 6) + (5 -> 9 -> 2). That is, 617 + 295. Output: 2 -> 1 -> 9. That is, 912.FOLLOW UP
假设数字以正序存储。重复上述问题。
EXAMPLE
Input: (6 -> 1 -> 7) + (2 -> 9 -> 5). That is, 617 + 295. 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
Input: A -> B -> C -> D -> E -> C [the same C as earlier] Output: C提示：#50, #69, #83, #90
附加问题：树和图(#4.3)，面向对象设计(#7.12)，系统设计和可扩展性(#9.5)，中等问题(#16.25)，困难问题(#17.12)。
提示从第 653 页开始。