看一遍就理解,图解单链表反转

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 看一遍就理解,图解单链表反转

前言

反转链表是程序员必备的基本素养,经常在面试、笔试的过程中出现。一直觉得反转链表实现代码不是很好理解,决定搬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指向了headhead不为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

参考与感谢

本人花费半年的时间总结的《Java面试指南》已拿腾讯等大厂offer,已开源在github ,欢迎star!

转载声明:转载请注明出处,本技术博客是本人原创文章

本文GitHub https://github.com/OUYANGSIHAI/JavaInterview 已收录,这是我花了6个月总结的一线大厂Java面试总结,本人已拿大厂offer,欢迎star

原文链接:blog.ouyangsihai.cn >> 看一遍就理解,图解单链表反转


 上一篇
我去,还在这样读写 excel 这也太低效了吧,好办法来了 我去,还在这样读写 excel 这也太低效了吧,好办法来了
  点击上方 **好好学java **,选择 **星标 **公众号 重磅资讯、干货,第一时间送达 今日推荐:牛人 20000 字的 Spring Cloud 总结,太硬核了~ 作者:楼下小黑哥 链接:https://www.cnblo
2021-04-04
下一篇 
只需 5 分钟看完这篇 HTTPS,去阿里面试和面试官扯皮就没问题了! 只需 5 分钟看完这篇 HTTPS,去阿里面试和面试官扯皮就没问题了!
  点击上方 **好好学java **,选择 **星标 **公众号 重磅资讯、干货,第一时间送达 今日推荐:牛人 20000 字的 Spring Cloud 总结,太硬核了~ 作者:肖萧 链接:https://segmentfault
2021-04-04