使用迭代方式解决“链表反转”问题

题目：反转链表
详细描述：给定一个单链表的头结点pHead(这个头节点是有值的，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
数据范围：0 ≤ n ≤ 1000
要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。
例如：如当输入链表{1,2,3}时，经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

转换过程如下图所示：

示例1
输入：{1,2,3}，返回值：{3,2,1}
示例2
输入：{}，返回值：{}
说明：空链表则输出空

解法1：
迭代，重复某一过程，每一次处理结果作为下一次处理的初始值，这些初始值类似于状态、每次处理都会改变状态、直至到达最终状态。从前往后遍历链表，将当前节点的next指向上一个节点，因此需要一个变量存储上一个节点prev，当前节点处理完需要寻找下一个节点，因此需要一个变量保存当前节点curr，处理完后要将当前节点赋值给prev，并将next指针赋值给curr，因此需要一个变量提前保存下一个节点的指针next
步骤：
1、将下一个节点指针保存到next变量 next = curr.next
2、将下一个节点的指针指向prev，curr.next = prev
3、准备处理下一个节点，将curr赋值给prev
4、将下一个节点赋值为curr，处理一个节点

package od;

/**
 * 使用迭代方式解决“链表反转”问题
 * 题目：给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
 * 原文地址：https://www.codernav.com/2775.html
 */
public class OdTest04 {
    static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

    }

    public static void main(String[] args) {
        // node1 -> node2 -> node3 -> node4 -> node5
        ListNode node5 = new ListNode(5, null);
        ListNode node4 = new ListNode(4, node5);
        ListNode node3 = new ListNode(3, node4);
        ListNode node2 = new ListNode(2, node3);
        ListNode node1 = new ListNode(1, node2);
        ListNode prev = f(node1);
        System.out.println(prev);
    }

    public static ListNode f(ListNode head) {
        // 后一个节点
        ListNode next;
        // 前一个节点
        ListNode prev = null;
        // 当前节点
        ListNode curr = head;
        // 循环结束条件：循环节点为空时
        while (curr != null) {
            // 保存指针
            next = curr.next;
            // 反转，将当前节点指向上一个节点
            curr.next = prev;
            // 把当前节点设置为前节点
            prev = curr;
            // 把当前节点指向后一个节点
            curr = next;
        }

        return prev;
    }
}

测试：在方法前后分别打断点，查看ListNode里的值。

反转前：ListNode的顺序是1>2>3>4>5

反转后：ListNode的顺序是5>4>3>2>1