双指针算法之快慢指针

小羽

2 minute read

在上一篇博文中，我们讨论了左右对撞指针，今天我们来讨论另外一种双指针算法——快慢指针。

I. 定义

快慢指针是双指针算法中的一种。不同于左右对撞指针，快慢指针中的两个指针是从同一侧但以不同的策略移动的指针。因此，两个指针中会有一个移动较快的快指针（fast）和一个较慢的慢指针（slow）。当快指针移动到数组的顶端时，停止遍历或进行新一轮遍历。

Note：由于链表中指针无法往回走的特性，快慢指针在链表中使用非常频繁。遇到链表题目时，应当考虑快慢指针。

II. 实现方法

实现快慢指针算法通常分为以下几个步骤：

  1. 将快慢两个指针指向集合的头部。
  2. 移动快指针到满足快慢指针的位置。
  3. 通过while循环使用快慢指针遍历集合。
  4. 返回结果

Note：为了避免fast指向null，有时需要将快慢指针指向集合的head的前一位。实现这个步骤，我们需要定义一个不干扰结果的对象dummy，并将它的next对象指向集合的head。

III. 经典习题

1) Remove Nth Node From End of List(Leetcode 19)

Given a linked list, remove the n-th node from the end of list and return its head.

图片名称

这道题目是一道典型的在链表上使用快慢指针解决的题目。题意为输入一个链表和一个Integer n，删除其从后往前数第n位的值，并返回新的链表。n的输入永远是合规的。

这道题目的解题 思路是这样的。我们设置快慢两个指针，令快指针先走n步，再同时移动快慢指针，直到快指针走到链表的底部。这时候删除慢指针指向的后一个对象，然后返回新的链表。

Note：为了避免输入长度为1的链表，删除其中唯一的一项时，快指针会首先走一位指向null的情况出现，我们要在链表的head前增设一个dummy对象。

解题步骤如下：

  1. 设置dummy对象其next指向head，避免fast指到null。
ListNode dummy = new ListNode(0);
dummy.next = head;
  1. 设置快慢两个指针指向dummy。
ListNode slow = dummy;
ListNode fast = dummy;
  1. 通过for循环让快指针先移动n次。
for (int i=0; i<n; i++){
  fast = fast.next;
}
  1. 通过while循环同时移动快慢两个指针，直到快指针指到链表的底部为止。
while(fast.next != null){
  slow = slow.next;
  fast = fast.next;
}
  1. 断开slow和它下一位的连接，并使其连接它的下下位，这样就完成了删除工作。
slow.next = slow.next.next;
  1. 返回新的链表。
return dummy.next;

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0); 
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;
        for (int i = 0; i<n;i++) {
            fast = fast.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}

2) Swap Nodes in Pairs(Leetcode 24)

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

图片名称

这道题的意思是输入一个链表，将其对象的位置两两互换（第一位和第二位互换，第三位和第四位互换…）

这道题的解题思路是这样的。首先令快指针比慢指针走的快一步，定义一个int i来计算对象的位置，是奇数位还是偶数位。如果是偶数位就把快慢两个指针的值互换，如果是奇数位就不变。接着开启while循环直到快指针指到null位置。最后返回链表。

解题步骤如下：

  1. 如果输入的链表为null，返回null。
if (head == null) return head;
  1. 定义快慢两个指针，慢指针指向头部，快指针指到第二位。
ListNode slow = head;
ListNode fast = head.next;
  1. 定义int i, 开启while循环，当快指针指到null时停止循环。如果i为偶数，交换快慢两个指针指向的对象的值，如果i为奇数则不变。
int i=0;
while(fast != null){
  if (i%2 == 0){
    int val = slow.val;
    slow.val = fast.val;
    fast.val = val;
  }
  slow = slow.next;
  fast = fast.next;
  i++;
}
  1. 返回新的链表。
return head;

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null) return head;
        ListNode slow = head;
        ListNode fast = head.next;
        int i = 0;
        while (fast != null){
            if (i%2 == 0){
                int val = slow.val;
                slow.val = fast.val;
                fast.val = val;
            }
            slow = slow.next;
            fast = fast.next;
            i++;
        }
        return head;
    }
}

IV. 总结

快慢指针算法是一种通常在链表中使用的功能强大的双指针算法。其步骤为设置快慢两个指针从同一个方向以不同的移动条件遍历集合从而达到相应的目的。