题解 | #反转链表#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode ReverseList (ListNode head) {
        ListNode prev = null;      // 初始化前一个节点为null
        ListNode current = head;  // 初始化当前节点为头节点
        
        while (current != null) {
            ListNode nextTemp = current.next;  // 临时保存下一个节点
            current.next = prev;               // 将当前节点的next指向前一个节点，实现反转
            prev = current;                    // 前一个节点移到当前节点
            current = nextTemp;                // 当前节点移到下一个节点
        }
        return prev; // 当current为null时，prev指向新的头节点
    }
}

反转链表是一个常见的算法问题。反转一个单链表意味着将链表的头变成尾，每个节点的下一个节点变成前一个节点。我们可以通过迭代的方式在一次遍历中完成这个操作，同时保证空间复杂度为 O(1)（因为我们只需要几个额外的指针）和时间复杂度为 O(n)（因为我们需要遍历一次链表）。

下面是这个算法的步骤：

1. 初始化两个指针，一个 prev 指向 NULL（前一个节点），一个 current 指向 pHead（当前节点）。
2. 遍历链表，对于每个节点：保存 current 的下一个节点，因为在调整链接后我们将失去对原来下一个节点的引用。将 current 的 next 指针指向 prev，实现反转。将 prev 移动到 current 的位置。将 current 移动到下一个节点的位置（在开始时已保存）。
3. 当 current 到达链表末尾（NULL）时，prev 将会指向新的头节点，因为原链表的最后一个节点现在是反转链表的第一个节点。
4. 返回 prev，它现在是反转后的链表的头节点。