剑指offer:反转链表

反转链表

http://www.nowcoder.com/questionTerminal/75e878df47f24fdc9dc3e400ec6058ca

思路:

  1. 题目所给的是单链表,想了一下反转后的样子:最后一个结点指向倒数第二个,倒数第二个指向倒数第三个,......,第二个指向第一个,第一个指向null;
  2. 知道了反转后各个结点指向哪之后,就需要开始调整每个结点的next指针。
  3. 这就需要把结点挨个从链表上摘下来,做调整;
  4. 这个调整过程需要两个指针辅助:pre记录其前一个结点位置,好让该结点的next指针指向前一个结点,但是在指向前一个结点前需要用一个指针p记录后一个结点地址,避免结点丢失。
  5. 例子:
    • 以head结点为例步骤如下:
    • 1.反转后head是指向null,所以未反转的时候其前一个结点应该是null,初始化pre指针为null;
    • 2.用p指针记录head的下一个结点head.next;
    • 3.从链表上摘下head,即让head.next指向pre;
    • 4.此时已完成head结点的摘取及与前一个节点的连接,则我们需要操作下一个结点:故需移动pre和head,让pre指向head,head指向下一个节点。
    • 重复这四个操作直到head走完原链表,指向null时,循环结束,返回pre。

答案:

public class Solution {
    public ListNode ReverseList(ListNode head) {
        //初始化pre指针,用于记录当前结点的前一个结点地址
        ListNode pre = null;
        //初始化p指针,用于记录当前结点的下一个结点地址
        ListNode p = null;
        //head指向null时,循环终止。
        while(head != null){
            //先用p指针记录当前结点的下一个结点地址。
            p = head.next;
            //让被当前结点与链表断开并指向前一个结点pre。
            head.next = pre;
            //pre指针指向当前结点
            pre = head;
            //head指向p(保存着原链表中head的下一个结点地址)
            head = p;
        }
        return pre;//当循环结束时,pre所指的就是反转链表的头结点
    }
}
全部评论
这不就是头插法建立链表吗
1 回复 分享
发布于 2020-12-12 16:20
多谢讲解 讲的太好了 !
1 回复 分享
发布于 2020-04-14 11:17
妙啊
点赞 回复 分享
发布于 2021-09-27 00:35
没看懂
点赞 回复 分享
发布于 2021-03-19 16:27
点赞 回复 分享
发布于 2020-10-08 12:53

相关推荐

弦五Strings:他之所以会举报你代课是因为在这种人眼里正常上课就是正义代课就是邪恶,典型二极管思维,处理方法就是私下沟通,你就说你自己家里经济困难或者家里父母生病什么之类的,需要去打工挣钱,用尽孝的正义对冲他认为的上课的正义,他可能就妥协了。
我的实习日记
点赞 评论 收藏
分享
06-26 22:20
门头沟学院 Java
码农索隆:让你把简历发给她,她说一些套话,然后让你加一个人,说这个人给你改简历,然后开始卖课
我的求职精神状态
点赞 评论 收藏
分享
评论
117
30
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务