4.3 双指针

所谓双指针是指利用两个指针来解决与链表相关的面试题，这是一种常用思路。双指针思路又可以根据两个指针不同的移动方式细分成两种不同的方法。第1种方法是前后双指针，即一个指针在链表中提前朝着指向下一个节点的指针移动若干步，然后移动第2个指针。前后双指针的经典应用是查找链表的倒数第k个节点。先让第1个指针从链表的头节点开始朝着指向下一个节点的指针先移动k-1步，然后让第2个指针指向链表的头节点，再让两个指针以相同的速度一起移动，当第1个指针到达链表的尾节点时第2个指针正好指向倒数第k个节点。

第2种方法是快慢双指针，即两个指针在链表中移动的速度不一样，通常是快的指针朝着指向下一个节点的指针一次移动两步，慢的指针一次只移动一步。采用这种方法，在一个没有环的链表中，当快的指针到达链表尾节点的时候慢的指针正好指向链表的中间节点。

下面采用双指针思路解决几道典型的链表面试题。

面试题21：删除倒数第k个节点

分析：如果可以遍历链表两次，那么这个问题就会变得简单一些。在第1次遍历链表时，可以得出链表的节点总数n。在第2次遍历链表时，可以找出链表的第n-k个节点（即倒数第k+1个节点）。然后把倒数第k+1个节点的next指针指向倒数第k-1个节点，这样就可以把倒数第k个节点从链表中删除。

但题目要求只能遍历链表一次。为了实现只遍历链表一次就能找到倒数第k+1个节点，可以定义两个指针。第1个指针P₁从链表的头节点开始向前走k步，第2个指针P₂保持不动；从第k+1步开始指针P₂也从链表的头节点开始和指针P₁以相同的速度遍历。由于两个指针的距离始终保持为k，当指针P₁指向链表的尾节点时指针P₂正好指向倒数第k+1个节点。

下面以在有6个节点的链表中找倒数第3个节点为例一步步分析这个过程。首先用第1个指针P₁从头节点开始向前走2步到达第3个节点，如图4.2（a）所示。然后初始化第2个指针P₂，让它指向链表的头节点，如图4.2（b）所示。最后让两个指针同时向前遍历，当指针P₁到达链表的尾节点时指针P₂刚好指向倒数第3个节点，如图4.2（c）所示。

找出链表中倒数第3个节点之后再删除倒数第2个节点比较容易，只需要把倒数第3个节点的next指针指向倒数第1个节点就可以。基于这种思路，可以编写出如下所示的代码：

由于当k等于链表的节点总数时，被删除的节点为原始链表的头节点，上述代码的逻辑也可以简化，运用哨兵节点来避免单独处理删除头节点的情况。

面试题22：链表中环的入口节点

分析：解决这个问题的第1步是如何确定一个链表中包含环。如果一个链表中没有环，那么自然不存在环的入口节点，此时应该返回null。

受到面试题21的启发，仍可以用两个指针来判断链表中是否包含环。和解决前面的问题一样，可以定义两个指针并同时从链表的头节点出发，一个指针一次走一步，另一个指针一次走两步。如果链表中不包含环，走得快的指针直到抵达链表的尾节点都不会和走得慢的指针相遇。如果链表中包含环，走得快的指针在环里绕了一圈之后将会追上走得慢的指针。因此，可以根据一快一慢两个指针是否能够相遇来判断链表中是否包含环。

❖ 需要知道环中节点数目的解法

第2步是如何找到环的入口节点，可以用两个指针来解决。先定义两个指针P₁和P₂，指向链表的头节点。如果链表中的环有n个节点，第1个指针P₁先在链表中向前移动n步，然后两个指针以相同的速度向前移动。当第2个指针P₂指向环的入口节点时，指针P₁已经围绕环走了一圈又回到了入口节点。

下面以图4.3中的链表为例来分析两个指针的移动规律。指针P₁在初始化时指向链表的头节点。由于环中有4个节点，指针P₁先在链表中向前移动4步到达第5个节点，如图4.4（a）所示。然后将指针P₂指向链表的头节点，如图4.4（b）所示。接下来两个指针以相同的速度在链表中向前移动直到相遇，它们相遇的节点正好是环的入口节点，如图4.4（c）所示。

最后一个问题是如何得到环中节点的数目。前面在判断链表中是否有环时用到了一快一慢两个指针。如果两个指针相遇，则表明链表中存在环。两个指针之所以会相遇是因为快的指针绕环一圈追上慢的指针，因此它们相遇的节点一定是在环中。可以从这个相遇的节点出发一边继续向前移动一边计数，当再次回到这个节点时就可以得到环中节点的数目。

下面的函数getNodeInLoop用一快一慢两个指针找到环中的一个节点，如果链表中没有环则返回null：

在找到环中任意一个节点之后，绕环一圈就能得出环中节点的数目，接下来再次使用双指针就能找到环的入口节点。相应的代码如下所示：

❖ 不需要知道环中节点数目的解法

上述代码需要求出链表的环中节点的数目。如果仔细分析，就会发现其实并没有必要求得环中节点的数目。如果链表中有环，快慢两个指针一定会在环中的某个节点相遇。慢的指针一次走一步，假设在相遇时慢的指针一共走了k步。由于快的指针一次走两步，因此在相遇时快的指针一共走了2k步。因此，到相遇时快的指针比慢的指针多走了k步。另外，两个指针相遇时快的指针比慢的指针在环中多转了若干圈。也就是说，两个指针相遇时快的指针多走的步数k一定是环中节点的数目的整数倍，此时慢的指针走过的步数k也是环中节点数的整数倍。

此时可以让一个指针指向相遇的节点，该指针的位置是之前慢的指针走了k步到达的位置。接着让另一个指针指向链表的头节点，然后两个指针以相同的速度一起朝着指向下一个节点的指针移动，当后面的指针到达环的入口节点时，前面的指针比它多走了k步，而k是环中节点的数目的整数倍，相当于前面的指针在环中转了k圈后也到达环的入口节点，两个指针正好相遇。也就是说，两个指针相遇的节点正好是环的入口节点。

简化之后的代码如下所示，和前面的代码相比，此处省略了得到环中节点的数目的步骤：

面试题23：两个链表的第1个重合节点

分析：很多应聘者都知道解决这个问题的蛮力法，即在第1个链表中顺序遍历每个节点，每遍历到一个节点时，在第2个链表中顺序遍历每个节点。如果在第2个链表中有一个节点和第1个链表中的某个节点相同，则说明两个链表在这个节点上重合，于是就找到了它们的公共节点。如果第1个链表的长度为m，第2个链表的长度为n，那么该方法的时间复杂度是O（mn）。

蛮力法通常不是最好的办法，下面分析有公共节点的两个链表有哪些特点，并从这些特点出发找出解决方法。

我们观察到的第1个特点是，可以在重合的两个链表的基础上构造一个包含环的链表。以图4.5中的两个链表为例，首先从第2个链表的头节点（值为7的节点）开始逐一遍历链表中的节点直至到达尾节点（值为6的节点）。如果把尾节点的next指针连接到第2个链表的头节点上，那么就可以构造出一个包含环的链表，如图4.6所示。接下来只需要从第1个链表的头节点开始找出环的入口节点（值为4的节点），该入口节点就是原来两个链表的第1个重合节点。

前面已经详细介绍了如何找出链表中环的入口节点，因此这里不再赘述。

我们观察到的第2个特点是如果两个链表有重合节点，那么这些重合节点一定只出现在链表的尾部。如果两个单向链表有重合节点，那么从某个节点开始这两个链表的next指针都指向同一个节点。在单向链表中，每个节点只有一个next指针，因此在第1个重合节点开始之后它们的所有节点都是重合的，不可能再出现分叉。

由于重合节点只可能出现在链表的尾部，因此可以从两个链表的尾部开始向前比较，最后一个相同节点就是我们要找的节点。但是在单向链表中，只能从头节点开始向后遍历，直至到达尾节点。最后到达的尾节点却要最先被比较，这就是通常所说的“后进先出”。至此不难想到可以用栈来解决这个问题：分别把两个链表的节点放入两个栈，这样两个链表的尾节点就位于两个栈的栈顶。接下来比较两个栈的栈顶节点是否相同。如果相同，则把栈顶节点弹出，然后比较下一个栈顶节点，直到找到最后一个相同的节点。

如果链表的长度分别为m和n，那么这种思路的时间复杂度是O（m+n）。上述思路需要用两个辅助栈，因此空间复杂度也是O（m+n）。和最开始的蛮力法相比，这是一种用空间换时间的方法。

前面的解法之所以需要使用栈，是因为我们希望能同时到达两个栈的尾节点。当两个链表的长度不相同时，如果从头开始遍历，那么到达尾节点的时间就不一致。其实，解决这个问题还有一个更简单的办法：首先遍历两个链表得到它们的长度，这样就能知道哪个链表比较长，以及长的链表比短的链表多几个节点。在第2次遍历时，第1个指针P₁在较长的链表中先移动若干步，再把第2个指针P₂初始化到较短的链表的头节点，然后这两个指针按照相同的速度在链表中移动，直到它们相遇。两个指针相遇的节点就是两个链表的第1个公共节点。

例如，在如图4.5所示的两个链表中，可以先各自遍历一次，得到链表的长度，分别为6和5，也就是说较长的链表比较短的链表多1个节点。第2次先用一个指针P₁在长的链表中走1步，到达值为2的节点。接下来把指针P₂初始化到短的链表的头节点（值为7的节点）。然后分别移动这两个指针直到找到第1个相同的节点（值为6的节点），这就是我们想要的结果。这个过程如图4.7所示。

理解这个过程之后就可以编写出如下所示的Java代码：

上述代码将两个链表分别遍历两次，第1次得到两个链表的节点数，第2次找到两个链表的第1个公共节点，这种方法的时间复杂度是O（m+n）。由于不需要保存链表的节点，因此这种方法的空间复杂度是O（1）。