迭代
解题思路
在遍历链表时，将当前节点的 next 指针改为指向前一个节点；
由于节点没有引用其前一个节点，因此必须事先存储其前一个节点；
在更改引用之前，还需要存储后一个节点；
最后返回新的头引用；
图解
复杂度
-
时间复杂度：
O(n)，其中 n 是链表的长度 -
空间复杂度：
O(1)
代码实现
function reverseList(head: ListNode | null): ListNode | null {
let prev = null; // 记录上一个节点
let cur = head; // 记录当前节点
// 当 cur 是节点时，进行迭代
while (cur) {
const next = cur.next; // 先保存当前节点的下一个节点
cur.next = prev; // 反转链表
prev = cur; // 向下移动链表
cur = next; // 取出存储的节点，继续循环
}
return prev;
};
递归
图解
利用尾递归，在回溯时修改各节点的 next 引用指向
复杂度
-
时间复杂度：
O(n)假设 n 是列表的长度； -
空间复杂度：
O(n)由于使用递归，将会使用隐式栈空间；
代码实现
function reverseList(head: ListNode | null): ListNode | null {
// 终止条件1：空链表直接返回
if (head === null) return head;
// 终止条件2：非空链表获取 倒数第二个节点
if (head.next === null) return head;
// 递归拿到最后一个节点，作为反转后的头结点
const prev = reverseList(head.next);
head.next.next = head; // 反转
head.next = null;
// 将拿到的反转后的头结点，一直向上返回
return prev;
};
头插法
迭代原有链表，利用头插法插入到新链表
辅助栈
迭代原有链表，将节点依次放到栈中，再遍历栈重新构建一个新链表
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
🌿 Git 进阶操作
上一篇
评论
