剑指 offer之反转链表_java

题目：反转链表

题目描述

输入一个链表，反转链表后，输出新链表的表头。

解题思路：迭代

假设存在链表 1 → 2 → 3 → Ø，我们想要把它改成 Ø ← 1 ← 2 ← 3。

在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。然后移动新链表的头指针，让它始终指向新链表头部，继续处理原链表的节点，即之前指针存放的后继，循环往复

代码实现：

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;//建立一个新的节点用来存放结果
		ListNode cur = head;
		while (cur != null) {
			// 先把后继节点保存起来
			ListNode Next = cur.next;
			cur.next = pre;
			// 各自往前走一步
			pre = cur;//移动新链表的头指针，让它始终指向新链表头部
			cur = Next;//继续处理原链表的节点，即之前指针存放的后继，循环往复
		}
        //返回新的头引用
		return pre;
    }
}