链表oj题_插入元素(链表)oj

1.力扣203.移除链表元素

思路：迭代，创建一个哨兵位，创建三个指针，第一个指针是cur，用来遍历的，第二个指针是next，他是cur的下一个节点，第三个是prev，他是用来和删除掉cur的后面的节点链接。
1

2.力扣206.反转链表

思路：创建一个头节点，然后依次调转方向
1

3.力扣876.链表的中间节点

思路：可以用快慢指针，慢指针一次走一步，快指针一次走两步，当快指针走到尾时，慢指针刚好到中间。
1

4.牛客：链表中倒数第k个节点

思路：也是利用快慢双指针，让fast先走k步，然后快慢同时走，fast到尾，slow就是倒数第k个节点
1

5.力扣21.合并两个有序链表

思路：创建一个头节点，然后比较两个链表，小的放里面，以此类推。
1

6.牛客.链表分割

思路：把链表分割成两段，一段存放小于x的，另外一段存放大于等于的，最后在链接，不要忘了合并的链表结尾的下一个节点要置空。
1

7.牛客.链表的回文结构

思路：先找到中间节点，然后把后半段倒置，在比较这两个部分
1

8.力扣160.相交链表

思路：分别计算A、B的长度，然后让长的先走它俩的差值，再一起走，相等就是相交的那个节点。
1

9.力扣141.环形链表

思路：可以用快慢指针，快指针一次走两步，慢指针一次走一步，如果有环，当他俩都进入环中时，走一步，他俩的差距缩小一步，最终一定会相遇。
1

10.力扣142.环形链表Ⅱ

思路：用快慢指针，快指针一次走两步，慢指针一次走一步
假设：链表头到环的入口的距离为a，快慢指针相遇在环中的b位置，环中剩余的为c
当慢指针进入环中，快指针不知道走了多少圈了，相遇的时候快指针走了n(b+c)+b+a


为什么慢指针没走完一圈就会被快指针追上呢？
当慢指针进入到环中时，此时快指针不知道在环中的哪个位置，设为x
他俩的距离就是b+c-x，快指针追上慢指针需要b+c-x步，x是>=0的
所以不管在什么地方相遇，慢指针都没走完一圈

所以就有了这个公式：a+n(b+c)+b=2(a+b)		2(a+b)：快指针是慢指针的两倍

推出来得a=nc+nb-b => a=c+(n-1)(b+c)
也就是，链表头到入环点的距离等于相遇点到入环点的距离加上快指针走了(n-1)(b+c)圈数

所以先找到快慢指针的交点，然后在让他俩同步走，一次一步，等到他俩相等的时候就是入环点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

11.力扣138.复制带随机指针的链表

思路：可以在原链表中每个节点后面链接一个复制的单个节点，先复制值，然后处理random指针，接着在剪切出来
1

12.力扣147.对链表进行插入排序

思路：先取一个数据做为假设排好序的序列，然后比较剩下链表的值和排好序列的值
有两种情况：
1.剩下的值小于排好的序列，直接头插
2.剩下的值大于排好的序列，插入到节点中间
1
2
3
4

13.牛客.删除链表中重复的节点

思路：运用三指针，题目可知，这个链表是排序的
NewNode指针用来链接
cur是链表的第一个节点
next是cur的下一个

用next来控制循环
有两点要注意：
1.因为链表是排序的，所以最后剩下一个节点的时候不需要在判断了
2.特殊情况，链表元素全是一样的，那么需要判断NewNode是否为空
1
2
3
4
5
6
7
8
9