建站
咨詢
售后
建站咨詢
新聞中心
前言
創(chuàng)新互聯(lián)公司成立于2013年，先為紅河等服務建站，紅河等地企業(yè)，進行企業(yè)商務咨詢服務。為紅河企業(yè)網(wǎng)站制作PC+手機+微官網(wǎng)三網(wǎng)同步一站式服務解決您的所有建站問題。
反轉(zhuǎn)鏈表是程序員必備的基本素養(yǎng)，經(jīng)常在面試、筆試的過程中出現(xiàn)。一直覺得反轉(zhuǎn)鏈表實現(xiàn)代碼不是很好理解，決定搬leetcode那道經(jīng)典反轉(zhuǎn)鏈表題出來，用十多張圖去解析它，希望加深大家對鏈表反轉(zhuǎn)的理解，謝謝閱讀。
leetcode的反轉(zhuǎn)鏈表原題&答案
題目描述： 反轉(zhuǎn)一個單鏈表。
- 輸入: 1->2->3->4->5->NULL
- 輸出: 5->4->3->2->1->NULL
分析：
假設存在鏈表 1 → 2 → 3 → ?，我們想要把它改成 ? ← 1 ← 2 ← 3。
在遍歷列表時，將當前節(jié)點的 next 指針改為指向前一個元素。由于節(jié)點沒有引用其上一個節(jié)點，因此必須事先存儲其前一個元素。在更改引用之前，還需要另一個指針來存儲下一個節(jié)點。不要忘記在最后返回新的頭引用!
代碼實現(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)代碼的實現(xiàn)
接下來，我們圖解以上代碼實現(xiàn)，先對以上實現(xiàn)代碼加上行號，如下：
- 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，所以這個即將要反轉(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)，圖解分析一波。
因為curr指向了head，head不為null，所以進入循環(huán)。先來看第5行：
- ListNode nextTemp = curr.next; //5
把curr.next 賦值給nextTemp變量，即nextTemp 指向curr的下一節(jié)點(即節(jié)點2)，可得圖如下：
再執(zhí)行到第6行：
- curr.next = prev; // 6
把prev賦值給curr.next,因為prev初始化化指向null，即curr(節(jié)點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í)行完 ListNodenextTemp=curr.next;后：
執(zhí)行完 curr.next=prev;后：
執(zhí)行完 prev=curr;后：
執(zhí)行完 curr=nextTemp;后：
來到這里，發(fā)現(xiàn)curr還是不為null，再回到while循環(huán)，再執(zhí)行一遍：
- ListNode nextTemp = curr.next; //5
- curr.next = prev; // 6
- prev = curr; //7
- curr = nextTemp; //8
依次可得圖：
來到這里，我們發(fā)現(xiàn)curr已經(jīng)為null了，可以跳出循環(huán)了。這時候prev指向的就是鏈表的反轉(zhuǎn)呀，所以第9行執(zhí)行完，反轉(zhuǎn)鏈表功能實現(xiàn)：
- return prev; //9
網(wǎng)頁標題：看一遍就理解，圖解單鏈表反轉(zhuǎn)
本文路徑：http://www.dlmjj.cn/article/djpccpi.html
