海外1核2G服务器低至2折,半价续费券限量免费领取!

搜搜吧

查看: 23|回复: 0

[资讯] 看一遍就理解,图解单链表反转

[复制链接]
  • TA的每日心情
    奋斗
    2020-2-21 10:30
  • 签到天数: 606 天

    [LV.9]以坛为家II

    硕士生

    1万

    主题

    1万

    帖子

    3万

    积分

    Rank: 8Rank: 8

    UID
    15343
    威望
    -561
    贡献
    8050
    在线时间
    302 小时
    注册时间
    2015-10-12
    发表于 2020-2-10 13:14 | 显示全部楼层 |阅读模式

    前言

    反转链表是程序员必备的基本素养,经常在面试、笔试的过程中出现。一直觉得反转链表实现代码不是很好理解,决定搬leetcode那道经典反转链表题出来,用十多张图去解析它,希望加深大家对链表反转的理解,谢谢阅读。

    250106914dbca3f2f8f7d7cc3ec7a6e5.jpg-wh_651x-s_1522474622.jpg

    leetcode的反转链表原题&答案

    题目描述: 反转一个单链表。

    • 输入: 1->2->3->4->5->NULL
    • 输出: 5->4->3->2->1->NULL

    分析:

    假设存在链表 1 → 2 → 3 → Ø,我们想要把它改成 Ø ← 1 ← 2 ← 3。

    在遍历列表时,将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点,因此必须事先存储其前一个元素。在更改引用之前,还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用!

    代码实现:

    •   public ListNode reverseList(ListNode head) {   
    •       ListNode prev = null;   
    •       ListNode curr = head;   
    •       while (curr != null) {   
    •           ListNode nextTemp = curr.next;
    •           curr.next = prev;
    •           prev = curr;
    •           curr = nextTemp;
    •       }
    •      return prev;
    • }

    图解链表反转代码的实现

    接下来,我们图解以上代码实现,先对以上实现代码加上行号,如下:

    •   public ListNode reverseList(ListNode head) {  //1
    •       ListNode prev = null;   // 2
    •       ListNode curr = head;   // 3
    •       while (curr != null) {   //4
    •           ListNode nextTemp = curr.next; //5
    •           curr.next = prev;  // 6
    •           prev = curr;  //7
    •           curr = nextTemp; //8
    •       }  
    •      return prev;  //9
    • }

    第一行代码图解

    • public ListNode reverseList(ListNode head) { //1

    我们顺着题目描述意思,假设链表就有1、2、3个元素吧,后面还跟着一个null,又因为输入是ListNode head,所以这个即将要反转的链表如下:

    6a44b180cc24c85de2e1796d97943739.png-wh_600x-s_2409814894.png

    第二行代码图解

    • ListNode prev = null; // 2

    将null赋值给prev,即prev指向null,可得图如下:

    8666568567c3b0aeaf0f77ec6a896ee5.png

    第三行代码图解

    • ListNode curr = head;

    将链表head赋值给curr,即curr指向head链表,可得图如下:

    4dc1e738b0aac51c9a40c417466fb1ab.png-wh_600x-s_540441028.png

    循环部分代码图解

    •   while (curr != null) {   //4
    •           ListNode nextTemp = curr.next; //5
    •           curr.next = prev;  // 6
    •           prev = curr;  //7
    •           curr = nextTemp; //8
    •       }

    循环部分是链表反转的核心部分,我们先走一遍循环,图解分析一波。

    因为curr指向了head,head不为null,所以进入循环。先来看第5行:

    • ListNode nextTemp = curr.next; //5

    把curr.next 赋值给nextTemp变量,即nextTemp 指向curr的下一节点(即节点2),可得图如下:

    8b98d862e85c038b9a9badc02965d829.png-wh_600x-s_2169136830.png

    再执行到第6行:

    • curr.next = prev; // 6

    把prev赋值给curr.next,因为prev初始化化指向null,即curr(节点1)指向了null,链表图解成这样了:

    7b91a2b913b93a15da4e2c481bacd238.png-wh_600x-s_1423482471.png

    然后我们看执行到第7行

    • prev = curr; //7

    把curr赋值给prev,prev指向curr,图解如下:

    679eb5ae9328da467b911305d647c107.png-wh_600x-s_1777872593.png

    接着,我们执行到第8行:

    • curr = nextTemp; //8

    把nextTemp赋值给curr,即curr指向nextTemp,图解如下:

    63ba80375ba5a4f6a7baed10c0d2fbf0.png-wh_600x-s_2225034483.png

    至此,第一遍循环执行结束啦,回到循环条件,curr依旧不为null,我们继续图解完它。

    5-8行代码又执行一遍,依次可得图:

    • ListNode nextTemp = curr.next; //5
    •          curr.next = prev;  // 6
    •          prev = curr;  //7
    •          curr = nextTemp; //8

    执行完 ListNodenextTemp=curr.next;后:

    791513a3ae5dd635ee2bc0bd54c472c8.png-wh_600x-s_854414913.png

    执行完 curr.next=prev;后:

    732de84cd4b9a3828eb88a76af5490d5.png-wh_600x-s_3797871578.png

    执行完 prev=curr;后:

    99bf23094991398719e45602ea969795.png-wh_600x-s_3266930557.png

    执行完 curr=nextTemp;后:

    84c7a9d720aaa7f6b7e0a39b5189a24f.png-wh_600x-s_283784691.png

    来到这里,发现curr还是不为null,再回到while循环,再执行一遍:

    • ListNode nextTemp = curr.next; //5
    • curr.next = prev;  // 6
    • prev = curr;  //7
    • curr = nextTemp; //8

    依次可得图:

    c92368e8b2d145c77f9b74e1d3e21c22.png-wh_600x-s_612778786.png


    874c317404f092b45b10bd88f878db50.png-wh_600x-s_2981625619.png


    1b067751f06e2696823327a68889efe0.png-wh_600x-s_2547690485.png


    3c4345b175c0c498aa8a9d491486c013.png-wh_600x-s_61816464.png

    来到这里,我们发现curr已经为null了,可以跳出循环了。这时候prev指向的就是链表的反转呀,所以第9行执行完,反转链表功能实现:

    • return prev; //9

    楼主热帖排行榜
    搜搜吧社区温馨提示:
    搜搜吧(www.sosoba.org)十分重视网络版权及其他知识产权的保护,针对网络侵权采取如下版权政策:
    1、本站有理由相信网友侵犯任何人的版权或作品,(图文,文字,下载,视频,非法传播),本站有权不事先通知即删除涉嫌侵权的作品和内容
    2、本站将采取必要的网络技术手段,确认为侵权作品或内容的用户有权进行警告、屏蔽、删除的行为,尽可能的防止侵权行为的发生
    3、搜搜吧影视资源均收集自互联网,没有提供影片资源存储,也未参与录制上传,若本站收录的资源涉及您的版权或知识产权或其他利益,我们会立即删除
    4、搜搜吧,删帖,投诉,举报,侵权,若本站侵犯您的权益,附上身份及权利证明,请直接发送邮件到 kefu-sosoba@qq.com 我们将在一个工作日内删除
    soso搜搜吧社区是聚合百度搜索,搜狗搜索,360搜索,新闻,教育,站长,广告,娱乐,影视,微信,网盘,营销,手机,汽车,游戏,论坛综合为一体的大型门户社区www.sosoba.org
    【腾讯云】腾讯云服务器安全可靠高性能,多种配置供您选择
    Powered by www.sosoba.org Copyright © 2013-2020 搜搜吧社区 小黑屋|手机版|地图|关于我们|腾讯云代金券|帮助中心|soso吧社区
    广告服务/项目合作: kefu-sosoba@qq.com  侵权举报邮箱: kefu-sosoba@qq.com  搜搜吧建站时间:创建于2013年07月23日
    免责声明:本站所有的内容均来自互联网以及第三方作者自由发布,版权归原作者版权所有,搜搜吧不承担任何的法律责任,若有侵权请来信告知,我们立即删除!

    GMT+8, 2020-2-21 13:11 , Processed in 1.110546 second(s), 12 queries , Gzip On, MemCache On.

    快速回复 返回顶部 返回列表