链表的题目一般都可以使用递归方法,但是注意一定要清楚链表操作,时用迭代法更加清晰

  1. 相交链表 双指针法,两个指针分别从A和B的头节点开始走到A的尾巴的节点从B的头节点开始,另外一个指针也是一样的,当两个指针相等的时候就可以退出了：
    • 长度相同,同时走到终点: 如果没有交点就返回nullptr
    • 长度不相同,那么就会同时走相同的距离,如果相遇得到的位置就是交点或者nullptr
  2. 反转链表 经典题目,迭代法或者递归法,利用两个指针即可,注意记录后面一个节点即可
  3. 回文链表 首先找到链表的中点,把中点和后面的部分反转,之后一个指针从头节点,另外一个指针从中间节点反转之后的位置开始查看位置是否相同
  4. 环形链表 两个指针,一个快指针,一个慢指针,fast的速度总是slow的两倍,如果相遇那么就是有环
  5. 环形链表II 上面的相遇点和头节点距离入环点的距离相同
  6. 合并两个有序链表 最好使用虚拟头节点,递归法和迭代法都可以使用,这里可以使用l1为基准,如果当前节点小于l1的位置,那么就需要把l2的节点插入到l1对应节点的前面,注意l2 的节点保持在虚拟头节点的位置即可,l1的位置不断移动即可,使用递归法更简单,判断当前节点大小即可
  7. 两数相加 递归法很妙,使用三个参数: l1 , l2 , carry(进位)作为入参,并且在l1为空的位置交换两个链表头节点是重点,迭代法中判断终止的条件就是两个都为空并且carry为0, 注意此时循环的迭代过程(相当于新建了一个链表)
  8. 删除链表倒数第N个节点 设置虚拟头节点,fast节点从头节点的位置开始走N个位置 , slow开始走,当fast走到尾节点的位置,slow的位置就是需要删除的节点的前面一个位置(虚拟头接电使用栈空间,利用RAII的思想)
  9. 两两交换链表中的节点 使用递归法或者迭代法,注意新的头节点是head -> next , 所以需要进行如下操作: auto newHead = head -> next , head -> next = swapPair(newHead -> next) , head -> next = new Head , 使用递归法还是用我的方法的,题解里面的方法不好理解
  10. k个一组反转链表 可以使用递归或者迭代法,利用递归法可以每一次判断长度,利用迭代法首先记录长度,之后不断把链表分组反转即可,这里可以利用虚拟头节点来此操作链表
  11. 随机链表复制 利用一个哈希表存储此时的链表和原来链表之间的关系即可
  12. 排序链表 使用归并排序,可以时用迭代法实现 #TODO可以使用快排实现
  13. 合并K个升序链表 两种方法:
    • 利用最小堆,把所有链表的头节点都加入到最小堆中,之后不断取出最小堆的顶端节点,并且把顶端节点的下一个节点加入到堆中(类似于合并链表)
    • 分治法: 相当于不断把数组分割开,知道只有一个链表此时就不需要分割了,需要使用递归和链表的合并(此时最后利用栈空间创建一个新的头节点并且不断向头节点中插入元素即可)
  14. LRU缓存 可以参考Java中的LinkedHashMap , 利用哈希表 + 双向循环链表来存储数据,其中哈希表用于存储 key 到节点的映射关系,双向循环链表记录插入时间的关系,比如不经常使用的节点就需要插入到后面,最终删除的时候也就只用删除后面的节点即可