递归反转链表

问题

给定一个单向链表的头节点，使用递归的方式将整个链表反转，并返回新的头节点。

例如：原链表为 1 -> 2 -> 3 -> 4 -> 5 -> null，反转后应该变为 5 -> 4 -> 3 -> 2 -> 1 -> null

解答

// 定义链表节点结构
class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

/**
 * 递归反转链表
 * @param {ListNode} head - 链表头节点
 * @return {ListNode} - 反转后的链表头节点
 */
function reverseList(head) {
  // 递归终止条件：空链表或只有一个节点
  if (head === null || head.next === null) {
    return head;
  }
  
  // 递归反转后面的链表，返回新的头节点
  const newHead = reverseList(head.next);
  
  // 关键步骤：将当前节点的下一个节点的 next 指向当前节点
  // 例如：1 -> 2 -> 3，当递归到节点1时，让节点2的next指向节点1
  head.next.next = head;
  
  // 将当前节点的 next 置为 null，防止形成环
  head.next = null;
  
  // 返回新的头节点（始终是原链表的最后一个节点）
  return newHead;
}

使用示例

// 辅助函数：创建链表
function createList(arr) {
  if (arr.length === 0) return null;
  const head = new ListNode(arr[0]);
  let current = head;
  for (let i = 1; i < arr.length; i++) {
    current.next = new ListNode(arr[i]);
    current = current.next;
  }
  return head;
}

// 辅助函数：打印链表
function printList(head) {
  const values = [];
  let current = head;
  while (current !== null) {
    values.push(current.val);
    current = current.next;
  }
  console.log(values.join(' -> '));
}

// 示例1：反转普通链表
const list1 = createList([1, 2, 3, 4, 5]);
console.log('原链表：');
printList(list1); // 1 -> 2 -> 3 -> 4 -> 5

const reversed1 = reverseList(list1);
console.log('反转后：');
printList(reversed1); // 5 -> 4 -> 3 -> 2 -> 1

// 示例2：反转只有一个节点的链表
const list2 = createList([1]);
console.log('\n单节点链表：');
printList(list2); // 1
const reversed2 = reverseList(list2);
printList(reversed2); // 1

// 示例3：反转空链表
const list3 = null;
console.log('\n空链表：');
const reversed3 = reverseList(list3);
console.log(reversed3); // null

关键点

• 递归终止条件：当链表为空或只有一个节点时，直接返回该节点，这是递归的基础情况

• 递归思路：先递归处理后续节点，得到反转后的新头节点，然后处理当前节点的指针反转

• 指针反转技巧：head.next.next = head 是操作，将下一个节点的 next 指针指向当前节点，实现反转

• 断开原连接：head.next = null 防止形成环形链表，确保链表尾部正确指向 null

• 返回值传递：每层递归都返回同一个新头节点（原链表的最后一个节点），确保最终返回正确的头节点

• 时间复杂度：O(n)，需要遍历所有节点

• 空间复杂度：O(n)，递归调用栈的深度等于链表长度