反转链表js实现
反转链表的 JavaScript 实现
反转链表是算法中的常见问题，以下是两种常用的实现方法：迭代法和递归法。
迭代法
迭代法通过遍历链表，逐个反转节点的指向来实现反转。
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。 - 遍历链表，保存当前节点的下一个节点
next。 - 将当前节点的
next指向prev，完成反转。 - 移动
prev和current指针，继续处理下一个节点。 - 最终
prev指向反转后的链表头节点。
递归法
递归法通过递归调用反转子链表，再处理当前节点。
function reverseList(head) {
if (head === null || head.next === null) {
return head;
}
const newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}- 递归终止条件：当前节点为
null或下一个节点为null，直接返回当前节点。 - 递归反转子链表，得到新的头节点
newHead。 - 将当前节点的下一个节点的
next指向当前节点，完成反转。 - 将当前节点的
next置为null，避免循环引用。 - 返回新的头节点
newHead。
示例用法
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);
// 输出反转后的链表
let current = reversedHead;
while (current !== null) {
console.log(current.val);
current = current.next;
}
// 输出: 5 4 3 2 1两种方法均能有效反转链表，迭代法空间复杂度为 O(1)，递归法空间复杂度为 O(n)。根据实际需求选择合适的方法。
