转载

剑指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;
    }
}

原文 https://segmentfault.com/a/1190000019823525

正文到此结束