/**
* 解法一:迭代(双指针)
* 思路:
* 我们可以设置两个指针,一个当前节点的指针,一个上一个节点的指针(初始为空)。
* 遍历整个链表,每到一个节点,断开当前节点与后面节点的指针,并用临时变量记录后一个节点,然后当前节点指向上一个节点。
* 再轮换当前指针与上-一个指针,让它们进入下一个节点及下一个节点的前序节点。
* 时间复杂度: O(n),遍历链表一次
* 空间复杂度: 0(1),无额外空间使用
*/
export function ReverseList(head: ListNode | null): ListNode | null {
if (!head) return head
let cur = head
let pre = null
while (cur != null) {
const temp = cur.next // 把后序的记下来
cur.next = pre
pre = cur
cur = temp
}
return pre
};
/**
* 解法二:递归
* 思路:
* 从上述方法一,我们可以看到每当我们反转链表的一个节点以后,要遍历进入下一个节点进入反转,
* 相当于对后续的子链表进行反转,这就是一个子问题,因此我们也可以使用递归。
* 时间复杂度:O(n),相当于递归遍历链表
* 空间复杂度:O(n),递归栈深度为链表长度n
*/
export function ReverseList(head: ListNode | null): ListNode | null {
if (!head || !head.next) return head
let node = reverseList(head.next)
head.next.next = head
head.next = null
return node
};
一站式解决前端面试高频算法题