单向链表逆置（单向链表逆置算法）

科技前沿 • 2025-05-26 10:39 • 阅读 51

大家好，我是讯享网，很高兴认识大家。

 <svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path> </svg>

讯享网

试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间复杂度为O(1)。

思路1

将头节点摘下，然后从第一节点开始，依次插入到头节点后面，头插法建立单链表，直到最后一个节点为止
![[Pasted image 20241102200949.png]]
讯享网

断开L和链表
![[Pasted image 20241102201609.png]]

将cur的next指向L的next
![[Pasted image 20241102201650.png]]

将L的next指向cur
![[Pasted image 20241102201710.png]]

完成插入，将cur指向next，next指向cur的next
![[Pasted image 20241102201756.png]]

讯享网

一个工作指针cur用来遍历链表，一个后继指针next用来保存cur的下一个节点
cur指向第一个节点，将哨兵位的next置为NULL，与后面的链表断开链接
cur往后遍历，直到cur指向NULL
将next指向cur的next，保存下一个节点
将cur的next指向哨兵位的next，将cur节点插入到哨兵节点之后
将L的next指向cur，将哨兵节点和当前节点进行链接
将cur指向next，继续往后遍历
最后返回链表L

思路2

用三个指针prev，cur，next来表示三个连续的节点
![[Pasted image 20241102202556.png]]

处理第一个节点，cur的next指向NULL
![[Pasted image 20241102202627.png]]

prev指向cur，cur指向next，next指向next的next
![[Pasted image 20241102202731.png]]

cur的next指向prev
![[Pasted image 20241102202824.png]]

直到next指向NULL
![[Pasted image 20241102202924.png]]

![[Pasted image 20241102203014.png]]

最后将L的next指向cur节点，也就是原来的尾节点
![[Pasted image 20241102203056.png]]

完成逆置

一个工作指针cur用来遍历链表，一个后继指针用来保存cur的下一个节点，一个前驱指针prev用来保存前一个节点
cur指向L的next，从第一个节点开始
将当前遍历的节点的next指向NULL
开始遍历：
将prev指向cur，cur指向next，next指向next的下一个，三个指针往后走一步
将cur的next指向perv，将中间节点的next指向前一个节点
直到第三个节点指向NULL，也就是最后一个节点的next指向倒数第二个节点
最后将L的next指向cur，也就是哨兵位头节点指向最后一个节点，完成逆置
返回链表L

设将n个整数存放到不带头结点的单链表L中，将L中保存的序列循环右移k个位置。例如，若k=1，则将链表{0,1,2,3}变为{3,0,1,2}。