反转链表
解法:多指针
1.创建三个指针
first:记录当前节点的 “前一个节点”(反转后,当前节点要指向它);second:指向当前正在处理的节点(每轮循环要反转它的next指针);third:暂存second的下一个节点(避免反转second的指针后,丢失后续链表)。
2.让third通过箭头移动,而first和second通过赋值移动,first、second、third指针通过循环依次向后挪位置,直至second=NULL
3.当循环结束时,所有的元素都被处理完毕,此时的指向是这样
需要为逆置后的新链表添加一个新的头结点,然后让新头结点的next指向“反转后的首元结点”(即原链表的尾结点first)
整体代码:
删除链表中间结点:快慢指针(fast/slow)
情况1:链表有奇数个结点(中间结点即为(n+1)/2)
情况2:链表有偶数个结点(中间结点为n/2+1)
大致做法:1.创建fast、slow两个指针,让slow指向链表的头结点,让fast指向链表的首元结点
2.fast和slow指针同时移动,fast每次移动两步,slow每次移动一步(fast移动的步长刚好为slow的两倍)
3.当fast=NULL(链表有偶数个结点)或者fast->next=NULL(链表有奇数个结点)时,表明fast已经遍历完整个链表,此时的slow恰好指向中间结点的前一个结点
与题目相关的截图来源于b站逊哥