js实现反向链表

反转链表的实现方法

反转链表是常见的算法问题，以下是使用JavaScript实现的几种方法。

迭代法

迭代法通过遍历链表并逐个反转节点指针实现。该方法时间复杂度为O(n)，空间复杂度为O(1)。

function reverseList(head) {
  let prev = null;
  let current = head;
  while (current !== null) {
    const nextTemp = current.next;
    current.next = prev;
    prev = current;
    current = nextTemp;
  }
  return prev;
}

递归法

递归法通过递归调用反转剩余链表，再处理当前节点。时间复杂度O(n)，空间复杂度O(n)（递归栈空间）。

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;
}

栈辅助法

利用栈的先进后出特性反转链表。时间复杂度O(n)，空间复杂度O(n)。

function reverseList(head) {
  if (!head) return null;
  const stack = [];
  let current = head;
  while (current) {
    stack.push(current);
    current = current.next;
  }
  const newHead = stack.pop();
  current = newHead;
  while (stack.length > 0) {
    const node = stack.pop();
    current.next = node;
    current = node;
  }
  current.next = null;
  return newHead;
}

注意事项

• 处理空链表或单节点链表的边界情况。
• 迭代法更节省内存，适合长链表。
• 递归代码简洁但可能有栈溢出风险。

以上方法均可实现链表反转，根据实际场景选择合适方案。