Leetcode之链表（简单难度篇）_哈希表边查找边添加

写在前面

第一次写博客（也是第一次刷题= =），主要是想把刷到的每一道题，都记录其解题思想和步骤。之后可以每隔一段时间就快速重温每一道题的解法与难点，达到重复记忆的效果。

leetcode前300道中的简单难度链表题

1.合并两个有序链表: 递归法、迭代法（最佳）

• 递归法：
  （1）递归边界：一个链表为null时返回另一个。
  （2）递归主线：哪个链表的结点值小，就将递归的结果更新为其next。
• 迭代法：
  （1）设立哨兵结点，为了容易返回合并后的链表。
  （2）在while循环前，维护一个prev指针（引用变量），持续从两个链表中选择较小的结点接到prev后边（先变prev.next，再统一变prev），直到其中一个为空。
  （3）循环结束后，将不为空的链表直接接到prev后边。

2.删除排序链表中的重复元素：维护一个current指针，只要非空且不是最后一个结点，就持续判断+改指针域(重复) / 后跳到current.next（没重复）。

注： <1> 因为循环里是current的数据域和current.next的数据域进行比较，而当最后一个结点是current时，它的next数据域为空，所以判断条件多了”不是最后一个结点“的限制。<2> current指针只会出现在每一个数字首次出现的位置上，当且仅当与current相等的数字都被跳过了，current才会移动到下一个数字上。因此当判断为重复时，仅改动了current.next（只改了current结点的指针域，并没有改变current的指向），只有不相等时才会让current=current.next。

3.判断环形链表：哈希表、双指针（最佳）

• 哈希表：一次遍历，边查找边添加。直到找到相同的地址，或者直到null退出循环。
• 双指针：
  （1）当为空链表或只有一个结点的链表时，无法成环。
  （2）若无环，快指针先到末尾。若有环，则快指针一定会与慢指针相遇。

注: <1>快指针到达末尾的判断条件有两种可能性（最后一个结点或null）。<2> 对于每一道题，都先考虑空链表和单个结点是不是特殊情况。

4.返回链表相交的起始结点：暴力法、哈希表、双指针（最佳）

• 双指针法：利用A*+B=B*+A，可以让两个指针同时到达相交点（A*是A在相交结点前的部分）。即使没有相交点，因为A+B=B+A，两个指针也可以同时到null，从而退出循环。

5.链表反转：递归法、迭代法（最佳）

• 递归法：从尾开始改
  （1）递归边界：对于空链表和单个结点，不用反转直接返回。
  （2）递归主线：保存返回的最后一个结点指针并层层返回。从倒数第二个结点开始，将它原本后一个结点的next域改为指向自己，并将自己的next域置为null。例如原始链表为1->2->3->-4>5，则递归过程为5->4>null，5->4->3->null，5->4->3->2->null，5->4->3->2->1->null。
• 迭代法：从头开始改
  （1）维护一个prev指针和current指针，current从head开始，始终指向prev的后一结点。
  （2）因为将current结点反转的过程中，需要改变其next域的指向。因此需要提前保存current的next值，反转完再赋回给current。

6.回文链表：双指针法（赋值到数组后），递归法，链表反转法（最佳）

• 链表反转法：
  （1）利用快慢指针找到中间结点，然后反转后半部分链表
  （2）比较原始链表与反转的链表，直到遇到反转链表的null。
  （3）恢复后半部分链表（即再反转一次）
• 双指针法判断回文的过程和【判断环形链表】时用的快慢指针类似，这里省略。
• 递归法：利用递归找到最后一个元素，并且用层层返回的trick模拟从后向前的反转链表，然后相当于两个链表进行比较。这个方法思路清奇，但是有丶难。

7.删除链表中的指定结点：将想要删除的结点的值替换为它后一个结点的值，并删除它的后一个结点。偷天换日，以假乱真。

总结

1.关于递归边界的妙用：

在第一题【合并有序链表】的递归边界时，null既判断了传入参数为空的情况，也判断了递归时到达一个链表末尾的情况（同理，【反转链表】时的递归边界即判断了空链表和单结点链表的情况，也判断了到达链表最后一个结点的情况），实现了巧妙的双重作用。可以推定，几乎所有的递归条件都有上述特性。但是，非递归法时就因题而异了。例如【删除重复元素】这一题中的非空条件仅用于判断传入空链表的情况（因为本题中current不能是最后一个结点，所以没办法到链表末尾之后的null）。讨论null的用法本身意义不大，但是可以帮助强化记忆解题思路。

2.while循环的判断条件

不同的题目，循环的截至点不同，常见的可分为以下两种情况：while(curr != null) 以及 while(curr.next !=null)。两者都可以使curr指针到达最后一个结点，区别在于对待最后一个结点的“态度”不同，前者可以“允许”对最后一个结点做一些操作（例如加入哈希表，或改变其next域实现反转等）。后者的写法虽然也能使curr指针到达最后一个结点，但是无法做任何操作，一到就立即退出循环。需要写成哪种因题而异。

while(curr != null)的情况：遍历所有结点（存入哈希表）的时候，当然需要对最后一个结点的内存地址也进行判断，看看有无重复，而不是一到最后一个结点就不加判断的退出循环。【反转链表】时需要将所有结点都反转，【合并两个有序链表】也是类似，循环条件为 l1 !=null && l2 != null。返回【相交链表的起始结点】的循环条件为：p!=null || q!=null。它们都需要对最后一个结点做处理。

while(curr.next != null)的情况：【删除有序链表的重复元素】时，由之前的讨论可知curr指针只会指向每个数字首次出现的位置，因此只要curr出现在最后一个结点，就说明一定不会有重复的情况，因此可以立即退出循环。

其他情况：【判断环形链表】时，由于有环的情况下快慢结点一定会相遇，因此循环条件为slow != fast。

3.双指针法和迭代法几乎总是最佳解法，太香了：）