大奖18dj18vip-大奖18dj18娱乐官网

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

大奖18dj18vip

查看: 45|回复: 0
打印 上一主题 下一主题

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

[复制链接]
  • TA的每日心情
    奋斗
    1 小时前
  • 签到天数: 614 天

    [LV.9]以坛为家II

    硕士生

    1万

    主题

    1万

    帖子

    3万

    积分

    Rank: 8Rank: 8

    UID
    15343
    威望
    -561
    贡献
    8056
    在线时间
    307 小时
    注册时间
    2015-10-12
    跳转到指定楼层
    楼主
    发表于 2020-2-10 13:14:40 | 只看该作者 |只看大图 回帖奖励 |倒序浏览 |阅读模式

    前言

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

    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,所以这个即将要反转的链表如下:

    第二行代码图解

    • ListNode prev = null; // 2

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

    第三行代码图解

    • ListNode curr = head;

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

    循环部分代码图解

    •   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),可得图如下:

    再执行到第6行:

    • curr.next = prev; // 6

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

    然后我们看执行到第7行

    • prev = curr; //7

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

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

    • curr = nextTemp; //8

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

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

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

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

    执行完 ListNodenextTemp=curr.next;后:

    执行完 curr.next=prev;后:

    执行完 prev=curr;后:

    执行完 curr=nextTemp;后:

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

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

    依次可得图:




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

    • return prev; //9

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

    GMT+8, 2020-3-16 15:15 , Processed in 1.134535 second(s), 10 queries , Gzip On, MemCache On.

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