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



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

思路1

将头节点摘下，然后从第一节点开始，依次插入到头节点后面，头插法建立单链表，直到最后一个节点为止

断开L和链表

将cur的next指向L的next

将L的next指向cur

完成插入，将cur指向next，next指向cur的next

一个工作指针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来表示三个连续的节点

处理第一个节点，cur的next指向NULL

prev指向cur，cur指向next，next指向next的next

cur的next指向prev

直到next指向NULL

最后将L的next指向cur节点，也就是原来的尾节点

完成逆置

一个工作指针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}。

算法思想

将n初始化为1，cur指向L，cur的next指向第一个节点，往后遍历直到cur的next指向NULL，cur指向最后一个节点

再下一次cur->next指向NULL，不进入循环
这样遍历出链表的节点个数

将cur的next指向L

构成循环链表
若k=1，也就是要右移一个位置
新链表的尾节点也就是第n-k个节点，也就是第4-1=3个节点
从头遍历依次，找到第n-k个节点，用cur指针指向

令L指向新链表尾节点的下一个节点

将cur的next指向NULL，断开环

完成右移

与逆置单链表的不同之处：

1. 初始化成循环链表而不是空链表
2. 判断链表尾不用空指针而用是否是链表头指针
   
   

让L的next指向自己，循环链表的初始化

用next指针指向cur的下一个节点

将cur的next指向L的next

L的next指向cur

cur指向next

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/76414.html