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

前言

创新互联公司成立于2013年，先为红河等服务建站，红河等地企业，进行企业商务咨询服务。为红河企业网站制作PC+手机+微官网三网同步一站式服务解决您的所有建站问题。

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

当前名称：看一遍就理解，图解单链表反转
地址分享：http://www.shufengxianlan.com/qtweb/news11/191661.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：创新互联

猜你还喜欢下面的内容