双指针+链表

这类题目第一步永远是指定头节点，有两种指定方法

  1. 虚拟头节点[需要新开链表存储结果]或是指定现有的输入头节点[不需要新开，比如快慢指针]，还有两种结合的
1
2
3
4
5
# 虚拟头节点 #指定现有的输入头节点
dummy = ListNode(-1)
p = dummy
p1 = l1
p2 = l2
1
2
# 快慢指针
fast, slow = head, head
  1. 开始遍历，一般while（90%）或for（1%）里再套一个if else
1
2
3
4
while fast and fast.next:
    # 慢指针走一步，快指针走两步
    slow = slow.next
    fast = fast.next.next
  1. 判断是否有结束条件[例如判断有环会有结束条件，判断中点没有]

备注：

  1. 哪有什么环会相遇算什么k减一，一句话：不是直线的情况下有速度差大概率会相遇。大道至简不就完了吗？

  2. 少写几行否则会超时

双指针+数组

区别：

  1. 不是p=head 而是定义起始的索引slow=0 fast=1
  2. while后面的语法变了（数组用数组的表示包括索引加一而不是点next）
1
2
3
4
5
6
7
8
while fast < len(nums):
       if nums[fast] != nums[slow]:
           slow += 1
           # 维护 nums[0..slow] 无重复
           nums[slow] = nums[fast]
       fast += 1
   # 数组长度为索引 + 1
   return slow + 1

一句话总结区别：用数组的语法表示代替链表，原理都一样

框架来自大量网络资料及labuladong算法笔记以及自己的理解。主打简化再简化以便于能记住