逆置单向链表
[!Tip]
本节源代码见Github链接🔗
问题描述
逆置单向链表
核心思路
通过遍历链表,依次逆置结点的next指向来解决。主要包含以下2步:
- 遍历链表;
- 在遍历过程中,用临时指针指向下一个结点,更新当前节点的next指针信息。
实现代码
【👉🏻>>点击展开查看代码】
/**
* 逆置单向链表
*
* @param headNode
* @return NormalListNode
* @author: Max Solider
* @date: 2022/10/9 14:18
*/
NormalListNode reverseList(NormalListNode headNode) {
if (headNode == null || headNode.getNext() == null) {
return headNode;
}
NormalListNode nextNode = null;
NormalListNode previousNode = null;
while (headNode != null) {
nextNode = headNode.getNext();
headNode.setNext(previousNode);
previousNode = headNode;
headNode = nextNode;
}
headNode = previousNode;
return headNode;
}
时间复杂度
时间复杂度为O(n),用于遍历链表。
空间复杂度
空间复杂度为O(1),用于存储临时变量。