反转链表js实现
反转链表的 JavaScript 实现
反转链表是常见的算法问题，可以通过迭代或递归两种方式实现。以下是两种方法的详细实现和解释。
迭代法
迭代法通过遍历链表并逐个反转节点指针实现反转。需要维护三个指针：prev、current 和 next。
function reverseList(head) {
let prev = null;
let current = head;
while (current !== null) {
const next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev;
}- 初始化指针：
prev初始化为null，current初始化为链表头head。 - 遍历链表：每次迭代保存
current.next到next，将current.next指向prev，然后移动prev和current。 - 返回新头节点：最终
prev成为反转后的链表头。
递归法
递归法通过递归调用反转子链表，并调整指针方向。
function reverseListRecursive(head) {
if (head === null || head.next === null) {
return head;
}
const newHead = reverseListRecursive(head.next);
head.next.next = head;
head.next = null;
return newHead;
}- 基线条件：如果链表为空或只有一个节点，直接返回
head。 - 递归反转：递归调用反转
head.next后的链表，得到新头节点newHead。 - 调整指针：将
head.next.next指向head，断开原head.next的链接。
示例测试
测试反转链表函数，确保其正确性。
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
// 创建链表 1 -> 2 -> 3 -> 4 -> 5
const head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
// 反转链表
const reversedHead = reverseList(head);
console.log(reversedHead); // 输出反转后的链表头复杂度分析
- 时间复杂度：两种方法均为 O(n)，需遍历链表所有节点。
- 空间复杂度：迭代法为 O(1)，递归法为 O(n)（递归栈空间）。
