剑指offer笔记// 15·反转链表

题目描述

输入一个链表，反转链表后，输出新链表的表头。
关键词：链表

思路

关键在于每一个结点的反转，想清楚每个节点的循环体内部后，思路就清晰了。
1.判断特殊情况，当链表为空，或者链表长度为1（head.next = null）时，不用反转，直接返回
2.定义pre，next分别保存循环时前一节点和后一个节点，初值为空。利用题给的head保存当前节点
3.执行循环，循环链表长度次，

循环体为：

• 更新next：next为正常顺序的head.next
• 更新head.next：head.next指向pre，
• 更新pre：pre = head
• 更新head：head = next右移

可以发现：主要时更新head的指向，pre和next的更新时为了配合next，head更新只是对应当前节点的移动，应为最后一步。

循环移动时，一般都遵循先记录，再更新的原则，因为pre的更新受限于head.next的更新，head.next的更新又受限于next的更新，所以更新顺序为

next——》head.next——》pre

——》head

4.终止条件与返回，当最后一次循环发生时，head = next，如果next为null，说明原来的数组到头了，此时，pre指向null之前的最后一个数。所以返回null，这样就可以实现链表反转，新的head是pre

代码实现

链接：https://www.nowcoder.com/questionTerminal/75e878df47f24fdc9dc3e400ec6058ca?answerType=1&f=discussion
来源：牛客网

public class Solution {
    public ListNode ReverseList(ListNode head) {
         //（选择）判断链表为空或长度为1的情况
        if(head == null || head.next == null){
            return head;
        }
        //（顺序）
        ListNode pre = null; // 当前节点的前一个节点
        ListNode next = null; // 当前节点的下一个节点
        //（循环）
        while( head != null){
            next = head.next; // 记录当前节点的下一个节点位置；
            head.next = pre; // 让当前节点指向前一个节点位置，完成反转
            pre = head; // pre 往右走
            head = next;// 当前节点往右继续走
        }
        return pre;
    }
}