算法（4th ed）(143)：基础——背包、队列和栈 5.7

(链表练习）

这部分练习是专门针对链表的。建议：使用正文中所述的可视化表达方式画图。

1.3.18　假设 x 是一条链表的某个结点且不是尾结点。下面这条语句的效果是什么？

x.next = x.next.next;

答：删除 x 的后续结点。

1.3.19　给出一段代码，删除链表的尾结点，其中链表的首结点为 first。

1.3.20　编写一个方法 delete()，接受一个 int 参数 k，删除链表的第 k 个元素（如果它存在的话）。

1.3.21　编写一个方法 find()，接受一条链表和一个字符串 key 作为参数。如果链表中的某个结点的 item 域的值为 key，则方法返回 true，否则返回 false。

1.3.22　假设 x 是一条链表中的某个结点，下面这段代码做了什么？

t.next = x.next;
x.next = t;

答：插入结点 t 并使它成为 x 的后续结点。

1.3.23　为什么下面这段代码和上一道题中的代码效果不同？

x.next = t;
t.next = x.next;

答：在更新 t.next 时，x.next 已经不再指向 x 的后续结点，而是指向 t 本身！

1.3.24　编写一个方法 removeAfter()，接受一个链表结点作为参数并删除该结点的后续结点（如果参数结点或参数结点的后续结点为空则什么也不做）。

1.3.25　编写一个方法insertAfter()，接受两个链表结点作为参数，将第二个结点插入链表并使之成为第一个结点的后续结点（如果两个参数为空则什么也不做）。

1.3.26　编写一个方法 remove()，接受一条链表和一个字符串 key 作为参数，删除链表中所有 item 域为 key 的结点。

1.3.27　编写一个方法max()，接受一条链表的首结点作为参数，返回链表中键最大的节点的值。假设所有键均为正整数，如果链表为空则返回 0。

1.3.28　用递归的方法解答上一道练习。

1.3.29　用环形链表实现Queue。环形链表也是一条链表，只是没有任何结点的链接为空，且只要链表非空则 last.next 的值为 first。只能使用一个 Node 类型的实例变量（last）。

1.3.30　编写一个函数，接受一条链表的首结点作为参数，（破坏性地）将链表反转并返回结果链表的首结点。

迭代方式的解答：为了完成这个任务，我们需要记录链表中三个连续的结点：reverse、first 和 second。在每轮迭代中，我们从原链表中提取结点 first 并将它插入到逆链表的开头。我们需要一直保持 first 指向原链表中所有剩余结点的首结点，second 指向原链表中所有剩余结点的第二个结点，reverse 指向结果链表中的首结点。

public Node reverse(Node x)
{
   Node first   = x;
   Node reverse = null;
   while (first != null)
   {
      Node second = first.next;
      first.next  = reverse;
      reverse     = first;
      first       = second;
   }
   return reverse;
}

在编写和链表相关的代码时，我们必须小心处理异常情况（链表为空或是只有一个或两个结点）和边界情况（处理首尾结点）。它们通常比处理正常情况要困难得多。

递归解答：假设链表含有 $N$ 个结点，我们先递归颠倒最后 $N-1$ 个结点，然后小心地将原链表中的首结点插入到结果链表的末端。

public Node reverse(Node first)
{
   if (first == null) return null;
   if (first.next == null) return first;
   Node second = first.next;
   Node rest = reverse(second);
   second.next = first;
   first.next  = null;
   return rest;
}

1.3.31　实现一个嵌套类 DoubleNode 用来构造双向链表，其中每个结点都含有一个指向前驱元素的引用和一项指向后续元素的引用（如果不存在则为 null）。为以下任务实现若干静态方法：在表头插入结点、在表尾插入结点、从表头删除结点、从表尾删除结点、在指定结点之前插入新结点、在指定结点之后插入新结点、删除指定结点。