看一遍就理解，图解单链表反转
共 2664字，需浏览 6分钟
·
2021-04-25 21:54
前言
反转链表是程序员必备的基本素养，经常在面试、笔试的过程中出现。一直觉得反转链表实现代码不是很好理解，决定搬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) { //1ListNode prev = null; // 2ListNode curr = head; // 3while (curr != null) { //4ListNode nextTemp = curr.next; //5curr.next = prev; // 6prev = curr; //7curr = 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) { //4ListNode nextTemp = curr.next; //5curr.next = prev; // 6prev = curr; //7curr = 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; //5curr.next = prev; // 6prev = curr; //7curr = nextTemp; //8
执行完ListNode nextTemp = curr.next;后：
执行完curr.next = prev;后：
执行完prev = curr;后：
执行完curr = nextTemp;后：
来到这里，发现curr还是不为null，再回到while循环，再执行一遍：
ListNode nextTemp = curr.next; //5curr.next = prev; // 6prev = curr; //7curr = nextTemp; //8
依次可得图：
来到这里，我们发现curr已经为null了，可以跳出循环了。这时候prev指向的就是链表的反转呀，所以第9行执行完，反转链表功能实现：
return prev; //9
腾讯、阿里、滴滴后台面试题汇总总结 — （含答案）
面试：史上最全多线程面试题 ！
最新阿里内推Java后端面试题
JVM难学？那是因为你没认真看完这篇文章
关注作者微信公众号 —《JAVA烂猪皮》
了解更多java后端架构知识以及最新面试宝典
看完本文记得给作者点赞+在看哦~~~大家的支持，是作者源源不断出文的动力