有用的算法技巧3.熟练使用双指针

3。巧妙使用双指针

双指针对于问单链表的问题特别有用，比如“找出单链表是否有环”、“如何做”。对于这类问题，我们可以使用双指针指针，方便多了。顺便告诉你如何使用双指针来解决这三个问题。

例如第一题

，我们可以设置一个慢速指针和一个快指针遍历链表，慢指针每次移动一个节点，快指针每次移动两个节点，如果链表不存在循环，则快指针先遍历链表，如果有循环循环中，第二次遍历时快指针与慢指针相遇

至第二题

快慢设置指针相同。慢速一次移动一个节点，而快速移动两个节点。遍历链表时，快指针移动完成后，慢指针就到达中心。

对于第三题

设置两个指针，其中一个先移动k个节点。此后，两个指针以相同的速度移动。当第一个移动指针遍历完成后，第二个指针正好位于倒数第 k 个节点处。

你看，用两只手方便多了。因此，当你以后处理一些与链表相关的问题时，你可能要考虑双指针。

作者：帅
来源：知乎