反转链表

问题

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

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

解答

链表节点定义

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

迭代法

function reverseList(head) {
  let prev = null;
  let curr = head;

  while (curr !== null) {
    // 保存下一个节点
    const next = curr.next;
    // 反转指针
    curr.next = prev;
    // 移动 prev 和 curr
    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;
}

测试代码

// 创建链表: 1 -> 2 -> 3 -> 4 -> 5
function createList(arr) {
  const dummy = new ListNode(0);
  let curr = dummy;
  for (const val of arr) {
    curr.next = new ListNode(val);
    curr = curr.next;
  }
  return dummy.next;
}

// 打印链表
function printList(head) {
  const result = [];
  while (head) {
    result.push(head.val);
    head = head.next;
  }
  console.log(result.join(' -> '));
}

const list = createList([1, 2, 3, 4, 5]);
printList(list); // 1 -> 2 -> 3 -> 4 -> 5

const reversed = reverseList(list);
printList(reversed); // 5 -> 4 -> 3 -> 2 -> 1

关键点

• 迭代法需要三个指针：prev、curr、next，逐个反转指针方向
• 递归法的关键是先递归到链表末尾，再从后往前修改指针
• 迭代法时间复杂度 O(n)，空间复杂度 O(1)
• 递归法时间复杂度 O(n)，空间复杂度 O(n)（调用栈）
• 注意处理空链表和单节点链表的边界情况