代码随想录刷题Day26

今天继续回顾关于双指针的使用。

反转字符串中的单词：这道题，双指针的作用是用来作为“单词”的界线划分，不过在使用双指针之前，需要预处理字符串，也就是把多个空格“压缩”为一个空格，这样在后续的双指针确定单词界线时候会更加好操作些。双指针划分好单词界线之后，使用reverse函数先对整个字符串翻转，接着是对单词部分再叠加一次原地翻转。

反转链表：这道题双指针是用在链表的next指针方向反转上，这里其实涉及到三个指针，但是next指针就像swap时候的temp变量的作用，只是暂存一个值而已，主要还是curr指针和pre指针，分别用来指向next指针方向反转的两个节点信息。

删除链表的倒数第N个节点:这道题，我当时自己做出来用的是栈结构的思想，这里使用快慢指针来定位倒数第N这个位置，大致过程如下：

链表相交：这道题，印象中是先找出两个·字符串中较短的那个，然后一个链表用一个指针同步遍历比较，直到出现两个负责不同链表的指针的内容一致的时候就返回。

环形链表II：这道题需要两次使用双指针。第一次是使用快慢指针，快指针一步两个节点，慢指针一步一个节点，直到相遇时候停止继续遍历；接着是再重新用两个步调一致的指针，也就是都是一步一个节点的指针，一个从链表头开始，一个指针从相遇点开始，直到两个指针相遇的地方，就是入环口位置。这个做法是有数学规律推导的。

三数之和、四数之和：这两个题都是使用双指针来减少一层的嵌套，双指针移动是根据和的大小和target值的大小比较来确定的，以及在移动过程中，要注意去重。

这两天看关于双指针的题目，还是觉得双指针的作用还是很多样的，不是局限于一种功能，可以大致分成以下类型：

• 两个指针，一个用于遍历，一个用于维护某种信息的数据，如移除元素、替换数字
• 两个指针的功能是类似的，主要功能均是遍历作用，如反转字符串、翻转链表、翻转字符串里的单词、链表相交、三数之和、四数之和
• 快慢指针，如删除链表的倒数第N个节点、环形链表II