看一遍就理解，圖解單鏈表反轉(zhuǎn)

前言

反轉(zhuǎn)鏈表是程序員必備的基本素養(yǎng)，經(jīng)常在面試、筆試的過(guò)程中出現(xiàn)。一直覺(jué)得反轉(zhuǎn)鏈表實(shí)現(xiàn)代碼不是很好理解，決定搬leetcode那道經(jīng)典反轉(zhuǎn)鏈表題出來(lái)，用十多張圖去解析它，希望加深大家對(duì)鏈表反轉(zhuǎn)的理解，謝謝閱讀。

leetcode的反轉(zhuǎn)鏈表原題&答案

題目描述： 反轉(zhuǎn)一個(gè)單鏈表。

輸入: 1->2->3->4->5->NULL輸出: 5->4->3->2->1->NULL

分析：

假設(shè)存在鏈表 1 → 2 → 3 → ?，我們想要把它改成 ? ← 1 ← 2 ← 3。

在遍歷列表時(shí)，將當(dāng)前節(jié)點(diǎn)的 next 指針改為指向前一個(gè)元素。由于節(jié)點(diǎn)沒(méi)有引用其上一個(gè)節(jié)點(diǎn)，因此必須事先存儲(chǔ)其前一個(gè)元素。在更改引用之前，還需要另一個(gè)指針來(lái)存儲(chǔ)下一個(gè)節(jié)點(diǎn)。不要忘記在最后返回新的頭引用！

代碼實(shí)現(xiàn)：

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;}

圖解鏈表反轉(zhuǎn)代碼的實(shí)現(xiàn)

接下來(lái)，我們圖解以上代碼實(shí)現(xiàn)，先對(duì)以上實(shí)現(xiàn)代碼加上行號(hào)，如下：

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

我們順著題目描述意思，假設(shè)鏈表就有1、2、3個(gè)元素吧，后面還跟著一個(gè)null，又因?yàn)檩斎胧荓istNode head，所以這個(gè)即將要反轉(zhuǎn)的鏈表如下:

第二行代碼圖解

ListNode prev = null;   // 2

將null賦值給prev，即prev指向null，可得圖如下：

第三行代碼圖解

ListNode curr = head;

將鏈表head賦值給curr，即curr指向head鏈表，可得圖如下：

循環(huán)部分代碼圖解

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

循環(huán)部分是鏈表反轉(zhuǎn)的核心部分，我們先走一遍循環(huán)，圖解分析一波。

因?yàn)?span style="font-weight: 700;">curr指向了head，head不為null，所以進(jìn)入循環(huán)。先來(lái)看第5行：

ListNode nextTemp = curr.next; //5

把curr.next 賦值給nextTemp變量，即nextTemp 指向curr的下一節(jié)點(diǎn)（即節(jié)點(diǎn)2），可得圖如下：

再執(zhí)行到第6行：

curr.next = prev;  // 6

把prev賦值給curr.next,因?yàn)閜rev初始化化指向null，即curr(節(jié)點(diǎn)1)指向了null，鏈表圖解成這樣了：

然后我們看執(zhí)行到第7行

 prev = curr;  //7

把curr賦值給prev，prev指向curr，圖解如下：

接著，我們執(zhí)行到第8行：

curr = nextTemp; //8

把nextTemp賦值給curr，即curr指向nextTemp，圖解如下：

至此，第一遍循環(huán)執(zhí)行結(jié)束啦，回到循環(huán)條件，curr依舊不為null，我們繼續(xù)圖解完它。

5-8行代碼又執(zhí)行一遍，依次可得圖：

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

執(zhí)行完ListNode nextTemp = curr.next;后：

執(zhí)行完curr.next = prev;后：

執(zhí)行完prev = curr;后：

執(zhí)行完curr = nextTemp;后：

來(lái)到這里，發(fā)現(xiàn)curr還是不為null，再回到while循環(huán)，再執(zhí)行一遍：

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

依次可得圖：

來(lái)到這里，我們發(fā)現(xiàn)curr已經(jīng)為null了，可以跳出循環(huán)了。這時(shí)候prev指向的就是鏈表的反轉(zhuǎn)呀，所以第9行執(zhí)行完，反轉(zhuǎn)鏈表功能實(shí)現(xiàn)：

 return prev;  //9

往期精彩推薦

騰訊、阿里、滴滴后臺(tái)面試題匯總總結(jié) — （含答案）

面試：史上最全多線程面試題 ！

最新阿里內(nèi)推Java后端面試題

JVM難學(xué)？那是因?yàn)槟銢](méi)認(rèn)真看完這篇文章

—END—

關(guān)注作者微信公眾號(hào) —《JAVA爛豬皮》

了解更多java后端架構(gòu)知識(shí)以及最新面試寶典

你點(diǎn)的每個(gè)好看，我都認(rèn)真當(dāng)成了

看完本文記得給作者點(diǎn)贊+在看哦~~~大家的支持，是作者源源不斷出文的動(dòng)力