反转链表

问题

给定单链表的头节点，反转链表并返回反转后的链表。

示例：

输入: 1 -> 2 -> 3 -> 4 -> 5
输出: 5 -> 4 -> 3 -> 2 -> 1

解答

方法一：迭代

function reverseList(head) {
  let prev = null;
  let curr = head;
  
  while (curr !== null) {
    const next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  
  return 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;
}

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: 迭代 O(1)，递归 O(n)

关键点

• 维护三个指针：prev、curr、next
• 按正确顺序更新指针
• 处理边界情况（空链表、单节点）