一 解析
鏈表內(nèi)包含一個(gè) val 數(shù)值和一個(gè)指向后繼節(jié)點(diǎn)的引用 next。要做的就是把這個(gè)鏈表節(jié)點(diǎn)內(nèi)的指針指向它的前驅(qū)節(jié)點(diǎn)。
因?yàn)檫@是一個(gè)單向鏈表，所以光憑借這個(gè)鏈表本身的數(shù)據(jù)還無(wú)法直接獲取每個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)。 所以這里我們需要一個(gè)額外的變量，來(lái)獲取并保存每個(gè)節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)。
初始化鏈表的頭節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)是 null。
這個(gè)題看起來(lái)很簡(jiǎn)單，但是很多時(shí)候，在我一段時(shí)間不接觸這個(gè)題之后再來(lái)做的時(shí)候，還是會(huì)出錯(cuò)。為了把這個(gè)題徹徹底底地梳理清楚，還是畫(huà)圖來(lái)處理的比較好。
問(wèn)題的核心，在于幾個(gè)指針的移動(dòng)過(guò)程，梳理清楚循環(huán)過(guò)程中指針的移動(dòng)，這個(gè)題就理清楚了。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode curr = head;
ListNode prev = null;
while (curr != null) {
ListNode item = curr.next;
curr.next = prev;
prev = curr;
curr = item;
}
return prev;
}
}
- 進(jìn)入循環(huán)體前，聲明了一個(gè)值為 null 的前驅(qū)節(jié)點(diǎn)，這個(gè)是符合場(chǎng)景的，因?yàn)槌跏兼湵淼念^節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)就是 null。
初始化
-
循環(huán)體第一步，聲明了一個(gè)新的指針，保存的是當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)引用。
step1 - 循環(huán)體第二步，將當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)引用修改為指向前驅(qū)節(jié)點(diǎn)。這里可以看到第一步代碼的作用了，只有先用指針保留對(duì)原來(lái)的后繼節(jié)點(diǎn)的引用，在修改了當(dāng)前節(jié)點(diǎn)的后繼引用指向之后，才能保持對(duì)鏈表后半段的控制。沒(méi)有這個(gè) item 指針，我們就無(wú)法繼續(xù)控制斷開(kāi)連接引用的兩段鏈表。
step2 - 第三步，將前驅(qū)節(jié)點(diǎn)指針指向修改為指向當(dāng)前節(jié)點(diǎn)。原來(lái)的鏈表頭節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)是 null，但是頭節(jié)點(diǎn)之后的節(jié)點(diǎn)，它們的前驅(qū)節(jié)點(diǎn)就都不是 null 了，所以需要在循環(huán)體內(nèi)不斷更新這個(gè)前驅(qū)節(jié)點(diǎn)指針的指向。
step3 - 第四步，將當(dāng)前節(jié)點(diǎn)指針引用修改為指向循環(huán)體內(nèi)保存的后繼節(jié)點(diǎn)。節(jié)點(diǎn) 1 的引用指向關(guān)系已經(jīng)修改完成了，下一輪循環(huán)需要處理的是節(jié)點(diǎn) 2。
step4
