前言

反轉鏈表是程序員必備的基本素養，經常在面試、筆試的過程中出現。一直覺得反轉鏈表實現代碼不是很好理解，決定搬leetcode那道經典反轉鏈表題出來，用十多張圖去解析它，希望加深大家對鏈表反轉的理解，謝謝閱讀。

leetcode的反轉鏈表原題&答案

題目描述： 反轉一個單鏈表。

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

分析：

假設存在鏈表 1 → 2 → 3 → Ø，我們想要把它改成 Ø ← 1 ← 2 ← 3。

在遍歷列表時，將當前節點的 next 指針改為指向前一個元素。由於節點沒有引用其上一個節點，因此必須事先存儲其前一個元素。在更改引用之前，還需要另一個指針來存儲下一個節點。不要忘記在最後返回新的頭引用！

代碼實現：

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

圖解鏈表反轉代碼的實現

接下來，我們圖解以上代碼實現，先對以上實現代碼加上行號，如下：

<code>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}/<code>

第一行代碼圖解

<code>public ListNode reverseList(ListNode head) {  //1/<code>

我們順著題目描述意思，假設鏈表就有1、2、3個元素吧，後面還跟著一個null，又因為輸入是ListNode head，所以這個即將要反轉的鏈表如下:

第二行代碼圖解

<code>ListNode prev = null;   // 2/<code>

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

第三行代碼圖解

<code>ListNode curr = head;/<code>

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

循環部分代碼圖解

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

循環部分是鏈表反轉的核心部分，我們先走一遍循環，圖解分析一波。

因為curr指向了head，head不為null，所以進入循環。先來看第5行：

<code>ListNode nextTemp = curr.next; //5/<code>

把curr.next 賦值給nextTemp變量，即nextTemp 指向curr的下一節點（即節點2），可得圖如下：

再執行到第6行：

<code>curr.next = prev;  // 6 /<code>

把prev賦值給curr.next,因為prev初始化化指向null，即curr(節點1)指向了null，鏈表圖解成這樣了：

然後我們看執行到第7行

<code> prev = curr;  //7/<code>

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

接著，我們執行到第8行：

<code>curr = nextTemp; //8/<code>

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

至此，第一遍循環執行結束啦，回到循環條件，curr依舊不為null，我們繼續圖解完它。

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

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

執行完ListNode nextTemp = curr.next;後：

執行完curr.next = prev;後：

執行完prev = curr;後：

執行完curr = nextTemp;後：

來到這裡，發現curr還是不為null，再回到while循環，再執行一遍：

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

依次可得圖：

來到這裡，我們發現curr已經為null了，可以跳出循環了。這時候prev指向的就是鏈表的反轉呀，所以第9行執行完，反轉鏈表功能實現：

<code>

作者：Jay_huaxiao
鏈接：https://juejin.im/post/5e3d3f25e51d45270c276fe3

閱讀更多 妖精的雜七雜八 的文章

關鍵字: 圖解 程序員 單鏈