链表算法常用技巧与操作

技巧

1. 引入虚拟头结点

一般适用于不带头节点的单向链表（即给定链表的第一个节点已经存放了有效数据）这种情况很多时候都需要考虑边界情况。这时候创建一个哨兵节点并连接第一个有效节点即可。

2.在两个双向节点中插入一个新节点cur

先让cur和后面的节点连，且连接的过程中都以prev（第一个节点）为视角，不然可能会在某个方向丢失第二个节点。再连prev。第一步prev->next->prev（第二个节点的prev)=cur，第二步cur->next=prev->next（cur和第二个结点已经完成双向连接）。第三步prev->next=cur,第四步cur->prev=prev。（顺序不可换）

我们也可以通过定义新变量优化，把第二个结点定义为next，那么就无所谓顺序问题，只要能连上即可（定义后就不会丢失结点）这里更推荐优化方法。

3.快慢双指针

可以解决判断链表是否有环、找链表中环的入口，链表中倒数第n个结点等问题

常用操作

1. 创建新节点——new

2. 尾插

先定义变量指向尾结点，然后改变该结点的next指向，然后重新定义新的尾结点！

3.头插

new一个虚拟头结点newhead，先让新结点->next=newhead->next，然后newhead->next=新节点。（创建newhead的目的是防止空链表的情况出错，此方法无论链表是否为空都适用）

用此方法逆序链表就非常简单了，创建一个只有newhead的空链表然后把原链表的节点从头到尾依次头插在新链表中