【算法】反转链表

难度：简单

题目

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

示例：

示例1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例2：
输入：head = []
输出：[]

提示：
● 链表中节点的数目范围是 [0, 5000]
● -5000 <= Node.val <= 5000

解题思路：

解这道题，关键是理解链表节点的连接关系以及如何通过改变节点的next指针来实现链表的反转。 关键的一点是先了解什么是链表，如果这个都不了解，肯定没法做出来。

1. 初始化：定义三个指针，prev（前一个节点）、curr（当前节点，初始为头节点）和next（下一个节点），用于在反转过程中跟踪和修改节点的连接关系。
2. 迭代：使用循环遍历链表，直到当前节点curr变为null，表示到达链表尾部。

• 在每一轮迭代开始时，先保存当前节点的下一个节点到next。
• 然后，改变当前节点的next指针，使其指向前一个节点prev。
• 接着，将curr和prev向前推进一步，即prev = curr，curr = next。

3. 处理头节点：遍历结束后，原来的尾节点将成为新的头节点，而原来的头节点将成为新的尾节点。因此，prev将指向新的头节点。

JavaScript实现：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
function reverseList(head) {
    let prev = null; // 前一个节点
    let curr = head; // 当前节点
    while (curr !== null) {
        let next = curr.next; // 保存当前节点的下一个节点
        curr.next = prev; // 将当前节点指向前一个节点，完成一次反转
        prev = curr; // 前一个节点向后移动
        curr = next; // 当前节点向后移动
    }
    return prev; // 最终prev会指向原链表的尾节点，即新链表的头节点
}