剑指offer反转链表Java

1. 问题描述

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

2. 思路

首先要判断给出的头节点是否为空，如果为空直接返回，如果不为空才可以进行反转。
因为每个节点只有一个 next 指针记录它的下一个节点的地址，所以应该需要两个变量分别记录当前节点左右两边的节点，否则反转链表之后就没办法连上后面的节点了。
通过循环遍历当前链表，在遍历过程中反转链表，当前节点遍历到最后为 null 时，循环停止，此时当前节点为 null，所以它的前一个节点就是新链表的第一个节点。
注意 ： 当前节点的前一个节点是从 null 开始的，当前节点一定要放在中间，记录它的前后各一个节点，否则循环过程易错。

/*
public class ListNode {
    int val;
    ListNode next = null;
 
    ListNode(int val) {this.val = val;}
}*/
public class Solution {public ListNode ReverseList(ListNode head) {if(head == null)
            return head;    //head 为 null 直接返回。ListNode pNode = head;    // 表示当前节点
        ListNode pre = null;    // 当前节点的前一个节点
        ListNode next = null;    // 当前节点的后一个节点
        while(pNode != null){
            next = pNode.next;    // 记录下当前节点的下一个节点
            pNode.next = pre; // 反转链表
            pre = pNode;    // 让 prej 和 pNode 都向后移动一位，next 不用变了，因为上面会自动根据 pNode 获取 next 节点。pNode = next;
        }
        return pre;
    }
}