快慢指针的思想

快慢指针的前进方向相同，且它们步伐的「差」是恒定的，根据这种确定性去解决链表中的一些问题。

。使用这种思想还可以解决链表的以下问题：

  • 第19题 倒数第 k 个结点：快指针先走K步，然后慢指针在去走。快指针是null的时候，慢指针就是当前倒数K节点。
  • 第 141 题环形链表：在环中的时候可以想象，A 同学开始有存款 100 元，每天赚 1 元，B 同学开始有存款 50 元，每天赚 2 元，B 同学一定会在某一天和 A 同学的存款一样；
  • 第 142 题：环形链表 II:链表的起点相同，使用快慢指针构造相同的长度让他们在圈里第一次相遇。然后把第一次的相遇的点慢指针不变，快指针指向头节点，然后重新执行再其次相遇就是入口节点。
  • 「力扣」第 161 题：相交链表，起点不同，构造相同长度让它们相遇，同样是利用了同步走这个等量关系。

使用两个指针变量同步移动，解决链表的问题常见的技巧还有：

  1. 使用递归函数，避免复杂的更改指针变量指向操作，使得求解问题变得简单
    1. 「力扣」第 206 题：反转链表；
    2. 「力扣」第 24 题：两两交换链表中的节点；
    3. 「力扣」第 25 题：K 个一组翻转链表；
    4. 「力扣」第 328 题：奇偶链表
    5. 「力扣」第 203 题：移除链表元素；
    6. 「力扣」第 21 题：合并两个有序链表。
  2. 设置「虚拟头结点」，避免对链表第 1 个结点做单独讨论，这个思想在数组里我们见过，叫「哨兵」；
    1. 「力扣」第 2 题：两数相加；
    2. 「力扣」第 82 题：删除排序链表中的重复元素 II。