2021.12.22 双指针
19. 删除链表的倒数第 N 个结点
面试题 02.07. 链表相交
142. 环形链表 II
15. 三数之和
今天没怎么认真刷题，重新做了几道简单题，回顾了一下双指针怎么用，只有最后一道题稍微有一点复杂。
19. 删除链表的倒数第 N 个结点
这道题比较简单，不过一开始没有想到最好的办法。先是遍历一遍链表计数，然后再次遍历，找到链表的倒数第N - 1个结点然后删除下一个结点。一共就只有三种情况：删除的节点在链表首位，在链表中间和在链表末尾。注意判断就行了。更好的办法可以只使用一次遍历解决问题。首先可以在链表头部加上dummy结点，由于要删除链表的倒数第N个结点，可以使用快慢指针，让快指针先走N + 1步，然后同时移动快慢指针，当快指针到达链表末尾null的时候，慢指针的下一个结点就是将要删除的结点。
面试题 02.07. 链表相交
这题同样也比较简单，如果要判断两个链表是否相交，可以使用两个指针分别从两个链表头部开始遍历，遍历到末尾时，再指向另一个链表的头部，这样遍历结束后，两个指针都会遍历完相等于两个链表长度和的结点，最后到达nullptr。如果两个链表相交，那么两个指针会在同一个节点相遇，如果不相交，会在最后的null结点相遇。
142. 环形链表 II
这个题做过几遍了，但是突然遇见的时候感觉还是有点想不出来。首先使用快慢指针判断链表是否存在环，快指针每次走两步，慢指针每次走一步，如果链表中存在环的话，那么最终快慢指针一定会相遇，否则快指针会先遍历到链表末尾。当快慢指针相遇时，快指针走过的节点数是慢指针的两倍，假设从节点头部走到链表中环的第一个结点的长度是a，慢指针总共走过的长度是x，那么快指针走过的程度就是2x， 因为快指针正好比慢指针多走了x步，而正好又多走了环一圈的长度，所以环的一圈长度正好是x。如果要找到环的初始结点，需要慢指针再走a个结点，而从链表头部到环的初始结点的长度正好是a个结点，所以可以将快指针指向链表的头结点，然后每次走一步，这样最终快慢指针就会在链表的头结点相遇。
15. 三数之和
这道题就比较复杂了，要使用双指针的方法求解三数之和的问题。因为使用哈希法来求解，不仅时间复杂度会高一些，同时因为这题要求不包含重复三元组所以去重的步骤很繁琐。首先将第一个指针i指向头一个数，然后后面两个指针分别指向i + 1和末尾，然后每次判断三数之和，如果和大了的话就将右指针向左移动，小了的话就将左指针向右移动，然后如果遇到与上一次相同的数就跳过。虽然思路比较简单，但是具体实现的时候还是有许多细节的的地方需要注意的。明天可以在复习一下。
