反转链表是什么？leetcode的反转链表原题&答案图解

2022-03-2709:36:53数据结构与算法Comments952 views字数 1885阅读模式

反转链表是程序员必备的基本素养，经常在面试、笔试的过程中出现。一直觉得反转链表实现代码不是很好理解，决定搬leetcode那道经典反转链表题出来，用十多张图去解析它，希望加深大家对链表反转的理解，谢谢阅读。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

leetcode的反转链表原题&答案

题目描述： 反转一个单链表。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

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

分析：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

假设存在链表 1 → 2 → 3 → Ø，我们想要把它改成 Ø ← 1 ← 2 ← 3。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

代码实现：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

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

图解链表反转代码的实现

接下来，我们图解以上代码实现，先对以上实现代码加上行号，如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

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

第一行代码图解

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

我们顺着题目描述意思，假设链表就有1、2、3个元素吧，后面还跟着一个null，又因为输入是ListNode head，所以这个即将要反转的链表如下:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

反转链表是什么？leetcode的反转链表原题&答案图解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

第二行代码图解

  1. ListNode prev = null; // 2

将null赋值给prev，即prev指向null，可得图如下：反转链表是什么？leetcode的反转链表原题&答案图解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

第三行代码图解

  1. ListNode curr = head;

将链表head赋值给curr，即curr指向head链表，可得图如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

反转链表是什么？leetcode的反转链表原题&答案图解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

循环部分代码图解

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

循环部分是链表反转的核心部分，我们先走一遍循环，图解分析一波。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

因为curr指向了head，head不为null，所以进入循环。先来看第5行：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

  1. ListNode nextTemp = curr.next; //5

把curr.next 赋值给nextTemp变量，即nextTemp 指向curr的下一节点（即节点2），可得图如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

反转链表是什么？leetcode的反转链表原题&答案图解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

再执行到第6行：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

  1. curr.next = prev; // 6

把prev赋值给curr.next,因为prev初始化化指向null，即curr(节点1)指向了null，链表图解成这样了：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

反转链表是什么？leetcode的反转链表原题&答案图解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

然后我们看执行到第7行文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

  1. prev = curr; //7

把curr赋值给prev，prev指向curr，图解如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

反转链表是什么？leetcode的反转链表原题&答案图解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

接着，我们执行到第8行：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

  1. curr = nextTemp; //8

把nextTemp赋值给curr，即curr指向nextTemp，图解如下：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

反转链表是什么？leetcode的反转链表原题&答案图解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

至此，第一遍循环执行结束啦，回到循环条件，curr依旧不为null，我们继续图解完它。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

5-8行代码又执行一遍，依次可得图：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

  1. ListNode nextTemp = curr.next; //5
  2. curr.next = prev; // 6
  3. prev = curr; //7
  4. curr = nextTemp; //8

执行完 ListNodenextTemp=curr.next;后：反转链表是什么？leetcode的反转链表原题&答案图解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

执行完 curr.next=prev;后：反转链表是什么？leetcode的反转链表原题&答案图解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

执行完 prev=curr;后：反转链表是什么？leetcode的反转链表原题&答案图解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

执行完 curr=nextTemp;后：反转链表是什么？leetcode的反转链表原题&答案图解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

来到这里，发现curr还是不为null，再回到while循环，再执行一遍：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

  1. ListNode nextTemp = curr.next; //5
  2. curr.next = prev; // 6
  3. prev = curr; //7
  4. curr = nextTemp; //8

依次可得图：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

反转链表是什么？leetcode的反转链表原题&答案图解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

反转链表是什么？leetcode的反转链表原题&答案图解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

反转链表是什么？leetcode的反转链表原题&答案图解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

反转链表是什么？leetcode的反转链表原题&答案图解文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

来到这里，我们发现curr已经为null了，可以跳出循环了。这时候prev指向的就是链表的反转呀，所以第9行执行完，反转链表功能实现：文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

  1. return prev; //9

 文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

作者：作者捡田螺的小男孩文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/23749.html

  • 本站内容整理自互联网，仅提供信息存储空间服务，以方便学习之用。如对文章、图片、字体等版权有疑问，请在下方留言，管理员看到后，将第一时间进行处理。
  • 转载请务必保留本文链接：https://www.cainiaoxueyuan.com/suanfa/23749.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定