逐对逆置链表
[!Tip]
本节源代码见Github链接🔗
问题描述
如何逐对逆置链表？例如，假设初始链表尾1->2->3->4->X，那么经过逐对逆置后，新链表应该为2->1->4->3->X
核心思路
通过递归或遍历，对链表元素进行逐对逆置，直到结束，或剩下单个结点。
实现代码
递归版本：
【👉🏻>>点击展开查看代码】
/**
* 逐对逆置链表-递归版本
*
* @author: Max Solider
* @date: 2022/10/9 21:58
* @param headNode
* @return org.example.linkedlist.normal.NormalListNode
*/
NormalListNode reversePairRecursive(NormalListNode headNode) {
// 递归的基本情形是遍历结束 或 只剩下最后一个结点
if (headNode == null || headNode.getNext() == null) {
return headNode;
}
// 成对逆置结点
NormalListNode tempNode = headNode.getNext();
headNode.setNext(tempNode.getNext());
tempNode.setNext(headNode);
headNode = tempNode;
headNode.getNext().setNext(reversePairRecursive(headNode.getNext().getNext()));
return headNode;
}
遍历版本：
【👉🏻>>点击展开查看代码】
/**
* 逐对逆置链表-遍历迭代版本
*
* @author: Max Solider
* @date: 2022/10/9 21:58
* @param headNode
* @return org.example.linkedlist.normal.NormalListNode
*/
NormalListNode reversePairIterative(NormalListNode headNode) {
if (headNode == null || headNode.getNext() == null) {
return headNode;
}
NormalListNode ptr1 = null;
NormalListNode ptr2 = null;
while (headNode != null && headNode.getNext() != null) {
if (ptr1 != null) {
ptr1.getNext().setNext(headNode.getNext());
}
ptr1 = headNode.getNext();
headNode.setNext(headNode.getNext().getNext());
ptr1.setNext(headNode);
if (ptr2 == null) {
ptr2 = ptr1;
}
headNode = headNode.getNext();
}
return ptr2;
}
时间复杂度
递归版本：时间复杂度为O(n)，用于遍历链表。
遍历版本：时间复杂度为O(n)，用于遍历链表。
空间复杂度
递归版本：空间复杂度为O(n)，用于栈空间。
遍历版本：空间复杂度为O(1)，用于存储临时变量。