剑指Offer——反转链表

题目描述

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

时间限制：1秒 空间限制：32768K 热度指数：482046

本题知识点： 链表

代码实现

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        //定义当前结点node并用head赋值，前一个结点pre，和后一个结点next
        //核心思想就是循环整个链表，然后反转每个结点的指针，使其由原来的指向下一个结点变为指向前一个结点，所以我们需要同时记录和更新当前结点，前一个结点和后一个结点
        //大概写一下步骤，因为我们修改当前结点指针后，整个链表就断裂了，所以我们需要记录前一个结点和后一个结点的信息
        // pre->node->next->next1 ======> pre<-node next->next1 
        ListNode node = head;
        ListNode pre = null;
        ListNode next = null;
        //while循环，终止条件是当前结点为空
        while(node != null){
            //首先更新next结点
            next = node.next;
            //把当前结点指针指向前一个结点
            node.next = pre;
            //更新前一个结点为当前结点
            pre = node;
            //更新当前结点为后一个结点
            node = next;
        }
        return pre;
    }
}

解题思路

首先我们需要知道链表的结构，链表是一个顺序表，每个结点存储着当前结点数据和指向下一个结点的指针。

我们想要反转链表，核心思想就是循环整个链表，然后反转每个结点的指针，使其由原来的指向下一个结点变为指向前一个结点，所以我们需要同时记录和更新当前结点，前一个结点和后一个结点。因为我们修改当前结点指针后，整个链表就断裂了，所以我们需要记录前一个结点 pre 和后一个结点 next 的信息。

我们通过画图的方式来看一下每一步的操作，为了方便理解，我在最前面和最后面增加了两个虚拟的空结点。

006tNc79ly1g3875ipaajj31bg0ik40t.png

最开始我们记录当前结点(node)、前一个结点(pre)和后一个结点(next)，然后改变当前结点的指针，使其指向前一个结点，然后更新前结点(node)、前一个结点(pre)和后一个结点(next)信息，然后再改变当前结点的指针，依次类推，直到当前结点为空的时候我们结束循环。然后此时前一个结点(pre)就是反转后的链表的表头。