看完这篇文章，你可以去 LeetCode 上解决以下问题：

本文结构，坐稳发车了🚗 我有特别的关于「快慢指针」的使用姿势 - 图1**

判断链表是否有环

LeetCode原题「LeetCode」环形链表

给定一个链表，判断链表中是否有环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

示例 1： 输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。如图：

image.png

解题思路一：HashSet

  1. /**
  2.  * Definition for singly-linked list.
  4.  * class ListNode {
  5.  *     int val;
  6.  *     ListNode next;
  7.  *     ListNode(int x) {
  8.  *         val = x;
  9.  *         next = null;
  10.  *     }
  11.  * }
  12.  */
  13. private boolean solution(ListNode head) {
  14.         HashSet<ListNode> nodes = new HashSet<>();
  15.         ListNode current = head;
  16.         while (current != null){
  17.             if (nodes.contains(current)){
  18.                 return true;
  19.             }else{
  20.                 nodes.add(current);
  21.                 current = current.next;
  22.             }
  23.         }
  24.         return false;
  25. }

空间复杂度：O(N) 时间复杂度：O(N)

解题思路二：快慢指针

  1. /**
  2.  * Definition for singly-linked list.
  4.  * class ListNode {
  5.  *     int val;
  6.  *     ListNode next;
  7.  *     ListNode(int x) {
  8.  *         val = x;
  9.  *         next = null;
  10.  *     }
  11.  * }
  12.  */
  13. private boolean solution(ListNode head) {
  14.         if (head == null || head.next == null){
  15.             return false;
  16.         }
  17.         ListNode slow = head, fast = head.next;
  18.         while (slow != fast){
  19.             if (fast == null || fast.next == null){
  20.                 return false;
  21.             }
  22.             fast = fast.next.next;
  23.             slow = slow.next;
  24.         }
  25.         return true;
  26. }

空间复杂度：O(N) 时间复杂度：O(1)

求有环链表环的起始位置

LeetCode原题「LeetCode」环形链表II

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。 说明：不允许修改给定的链表。

输入：head = [3,2,0,-4], pos = 1 输出：tail connects to node index 1 解释：链表中有一个环，其尾部连接到第二个节点。

同判断链表有环的问题，这道题也可以利用HashSet解题，我们主要看下快慢指针的解法：

/**
     * Definition for singly-linked list.
     *  * class ListNode {
     *  *     int val;
     *  *     ListNode next;
     *  *     ListNode(int x) {
     *  *         val = x;
     *  *         next = null;
     *  *     }
     *  * }
     */
    public ListNode solution(ListNode head) {
        boolean hasCycle = false;
        ListNode fast = head, slow = head;
        while (fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast){
                hasCycle = true;
                break;
            }
        }
        // 上面代码同链表有环的代码：判断链表是否有环，求出相遇点
        // 下面代码是解题的关键，相遇后，重置其中一个指针至头节点，再让两个指针以相同的速度继续遍历
        // 再次相遇两个指针指的节点即为环的起始位置
        slow = head;
        if (hasCycle){
            while(slow != fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;

        }else {
            return null;
        }
    }

寻找链表的中点

同样的，让快指针每次移动两步，慢指针每次移动一步。这样，当快指针到达链表尾部时，慢指针所处的位置就是链表的中点。

while(fast != null && fast.next != null){
    fast = fast.next.next;
    slow = slow.next;
}
// 此时，slow处于链表的中点位置
return slow;

寻找链表的倒数第 k 个元素

类似于寻找链表的中点思路，寻找链表的倒数第 k 个元素应该怎么做呢(把大象装进冰箱需要几步)？
分三步🚶：

  • 快指针先移动 k 个元素(k 不大于 链表长度)
  • 快慢指针每次同时移动一步
  • 快指针抵达链表尾部时，慢指针所处的位置就是链表的第 k 个元素。
// 快指针先移动k步
while(k-- > 0){
    fast = fast.next;
}

while(fast != null){
    fast = fast.next;
    slow = slow.next;
}
return slow;