When handle list, be careful of null value
2.1 编写代码，移除未排序链表中的重复结点。 进阶 如果不得使用临时缓冲区，该怎么解决？（第48页）
需要设法记录有哪些是重复的。这里只要用到一个简单的 散列表。 在下面的解法中，我们会直接迭代访问整个链表，将每个结点加入散列表。若发现有重复元 素，则将该结点从链表中移除，然后继续迭代。
进阶：不得使用缓冲区 如不借助额外的缓冲区，可以用两个指针来迭代：current迭代访问整个链表，runner用于 检查后续的结点是否重复。这段代码的空间复杂度为O(1)，但时间复杂度为O(N 2 )。
2.2 实现一个算法，找出单向链表中倒数第k个结点。（第 48 页）
解法 1：链表长度已知 若链表长度已知，那么，倒数第k个结点就是第(length - k)个结点。直接迭代访问链表就 能找到这个结点。
一种效率更高但不太直观的解法是以迭代方式实现。我们可以使用两个指针p1和p2，并将它 们指向链表中相距k个结点的两个结点，具体做法是先将p1和p2指向链表首结点，然后将p2向前 移动k个结点。之后，我们以相同的速度移动这两个指针，p2会在移动LENGTH - k步后抵达链表 尾结点。此时，p1会指向链表第LENGTH - k个结点，或者说倒数第k个结点。
2.3 实现一个算法，删除单向链表中间的某个结点，假定你只能访问该结点。（第 48 页）
在这个问题中，你访问不到链表的首结点，只能访问那个待删除结点。解法很简单，直接将 后继结点的数据复制到当前结点，然后删除这个后继结点。
，若待删除结点为链表的尾结点，则这个问题无解。没关系，面试官就是想要你指出这 一点，并讨论该怎么处理这种情况。例如，你可以考虑将该结点标记为假的。
2.5 给定两个用链表表示的整数，每个结点包含一个数位。这些数位是反向存放的，也就 是个位排在链表首部。编写函数对这两个整数求和，并用链表形式返回结果。 进阶 假设这些数位是正向存放的，请再做一遍。（第 49 页）
进阶 从概念上来说，第二部分并无不同（递归，进位处理），但在实现时稍微复杂一些。
(1) 一个链表的结点可能比另一个链表的少，我们无法直接处理这种情况。例如，假设要对 (1 -> 2 -> 3 -> 4)与(5 -> 6 -> 7)求和。务必注意，5应该与2而不是1配对。对此，我们可 以一开始先比较两个链表的长度并用零填充较短的链表。
(2) 在前一个问题中，相加的结果不断追加到链表尾部（也即向前传递）。这就意味着递归调 用会传入进位，而且会返回结果（随后追加至链表尾部）。不过，这里的结果要加到首部（也即 向后传递）。跟前一个问题一样，递归调用必须返回结果和进位。实现也不是太难，但处理起来 会更难一些，可以通过创建一个PartialSum包裹类来解决这一点。
2.6 给定一个有环链表，实现一个算法返回环路的开头结点。（第 49 页）
第 1 部分：检测链表是否存在环路 检测链表是否存在环路，有一种简单的做法叫FastRunner/SlowRunner法。FastRunner一次 移动两步，而SlowRunner一次移动一步。这就好比两辆赛车绕着同一条赛道以不同的速度前进， 最终必然会碰到一起。
聪明的读者可能会问：FastRunner会不会刚好“越过”SlowRunner，而不发生碰撞呢？绝 无可能。假设FastRunner真的越过了SlowRunner，且SlowRunner处于位置i，FastRunner处于 位置i + 1。那么，在前一步，SlowRunner就处于位置i - 1，FastRunner处于位置((i + 1) -2)或i - 1。也就是说，两者碰在一起了。
第 2 部分：什么时候碰在一起？
第 3 部分：如何找到环路起始处？
第 4 部分：将全部整合在一起
2.7 编写一个函数，检查链表是否为回文。（第 49 页）
解法 1：反转并比较
第一种解法是反转整个链表，然后比较反转链表和原始链表。若两者相同，则该链表为回文。 注意，在比较原始链表和反转链表时，其实只需比较链表的前半部分。若原始链表和反转链 表的前半部分相同，那么，两者的后半部分肯定相同。
解法 2：迭代法 要想探测链表的前半部分是否为后半部分反转而成，该怎么做呢？只需将链表前半部分反 转，可以利用栈来实现。 我们需要将前半部分结点入栈。根据链表长度已知与否，入栈有两种方式。 若链表长度已知，可以用标准for迭代访问前半部分结点，将每个结点入栈。当然，要小心处 理链表长度为奇数的情况。 若链表长度未知，可以利用本章开头描述的快慢runner方法迭代访问链表。在迭代循环的每 一步，将慢速runner的数据入栈。在快速runner抵达链表尾部时，慢速runner刚好位于链表中间位 置。至此，栈里就存放了链表前半部分的所有结点，不过顺序是相反的。 接下来，我们只需迭代访问链表余下结点。每次迭代时，比较当前结点和栈顶元素，若完成 迭代时比较结果完全相同，则该链表是回文序列。