反转链表的算法与实现 - 详细步骤与代码示例

反转链表是一个常见的算法问题，通常用于面试和算法练习中。链表是一种线性数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。反转链表意味着改变链表的方向，使得链表的头节点变为尾节点，尾节点变为头节点。

反转链表的步骤

1. 初始化三个指针：

   • prev：指向当前节点的前一个节点，初始为 null。
   • curr：指向当前节点，初始为链表的头节点。
   • next：指向当前节点的下一个节点，初始为 null。

2. 遍历链表：

   • 在遍历过程中，首先保存当前节点的下一个节点（next = curr.next）。
   • 然后将当前节点的 next 指针指向 prev（curr.next = prev）。
   • 接着将 prev 和 curr 指针向前移动（prev = curr，curr = next）。

3. 终止条件：

   • 当 curr 为 null 时，遍历结束，此时 prev 指向新的头节点。

代码实现

以下是使用 JavaScript 实现反转链表的代码：

function reverseLinkedList(head) {
    let prev = null;
    let curr = head;
    let next = null;

    while (curr !== null) {
        next = curr.next; // 保存下一个节点
        curr.next = prev; // 反转当前节点的指针
        prev = curr;      // 移动 prev 和 curr 指针
        curr = next;
    }

    return prev; // prev 是新的头节点
}

示例

假设有一个链表 1 -> 2 -> 3 -> 4 -> 5，反转后的链表应该是 5 -> 4 -> 3 -> 2 -> 1。

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

// 创建链表 1 -> 2 -> 3 -> 4 -> 5
let head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);

// 反转链表
let reversedHead = reverseLinkedList(head);

// 输出反转后的链表
let result = [];
while (reversedHead !== null) {
    result.push(reversedHead.val);
    reversedHead = reversedHead.next;
}
console.log(result); // 输出: [5, 4, 3, 2, 1]

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。我们需要遍历链表一次。
• 空间复杂度：O(1)，我们只使用了常数个额外的指针。

总结

反转链表是一个基础但重要的算法问题，理解并掌握它有助于加深对链表数据结构的理解。在实际开发中，链表操作虽然不如数组常见，但在某些场景下（如内存管理、LRU缓存等）仍然非常有用。