链表

链表

主要考察

• 链表的遍历
• 有环链表
• 双指针

从后向前遍历单链表

从前向后遍历时，使用一个队列来保存遍历的节点，每次从头部插入新节点

该方法可以实现翻转链表

O(1)时间内删除链表中的指定节点

• 删除的节点不是尾部节点： 使用待删除的节点的next节点值覆盖当前节点值，然后删除下一个节点
• 删除的节点是尾部节点且等于头节点，只剩一个节点 ： 将头节点置为null
• 删除的节点是尾节点且前面还有节点：遍历到末尾的前一个节点删除

复制带随机指针的链表

letcode传送门

• 首先通过next遍历链表，使用一个栈st保存每个节点
• 然后使用st克隆一堆链表节点nodes，不带next和random属性
• 遍历st，根据st.indexOf扎到随机节点的索引值index，依次设置每个节点的random为nodes[index]和next为nodes[i+1]

判断链表是否有环

使用快慢指针，快指针每次移动两步、慢指针每次移动一步，如果在某个时刻快慢指针重合则表示有环

如果链表有环，找到入环节点

letcode传送门

• 首先使用快慢指针判断有环，并从第一次相遇的节点开始进行标记count，
• 然后继续循环count++至第二次相遇时，此时count表示的就是环的长度
• 得到环的长度之后，将快慢指针同时指向head，并将快指针提前移动count步，后续每次循环时快慢指针都走一步，下次相遇时则为开始起环的节点

约瑟夫环

0,1,...,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

• 用链表模拟一个环
• 模拟游戏场景
• 记录头节点的前一个节点current，以保证我们找到的要删除的节点是current.next
• 每次循环m次找到目标节点删除，直到链表只剩下一个节点

参考:数组、链表、递归三种方式解决约瑟夫环

判断链表是否相交

https://leetcode-cn.com/explore/learn/card/linked-list/194/two-pointer-technique/746/

把两个单链表看作是两段线段，以两条线段相加的和不变这个条件，分别遍历两个链表。

参考: https://blog.csdn.net/qq_34364995/article/details/80518198

现有线段ACD和线段BCD，两条线段相交于C点。同时从A、B分别开始遍历ACD和BCD，遍历点记为PA和PB，经过的长度用len记录，遍历步长为1。当PA遍历到D时，PB在I，此时len为5。由于ACD已经遍历完，PA就跳到B点开始遍历BCD。当BCD遍历完时，PB跳转到A。

分解一下PA和PB的遍历轨迹就是，

• PA：AECHIDBFGC。
• PB：BFGCHIDAEC。

两个链表的公共节点

使用快慢指针

• 先找到两个链表的长度length1、length2
• 让长一点的链表先走length2-length1步，让长链表和短链表起点相同
• 两个链表一起前进，比较获得第一个相等的节点

删除倒数第k个节点

先遍历获取链表的长度len，然后再遍历到len-k处删除节点，需遍历两次

可以优化为：使用快慢指针，快指针先移动k步，然后快慢指针一起移动，当快指针到达末尾时，慢指针对应的就是第k个节点