一 解析
鏈表內(nèi)包含一個 val 數(shù)值和一個指向后繼節(jié)點(diǎn)的引用 next攻锰。要做的就是把這個鏈表節(jié)點(diǎn)內(nèi)的指針指向它的前驅(qū)節(jié)點(diǎn)娶吞。
因?yàn)檫@是一個單向鏈表械姻,所以光憑借這個鏈表本身的數(shù)據(jù)還無法直接獲取每個節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)。 所以這里我們需要一個額外的變量绣夺,來獲取并保存每個節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)欢揖。
初始化鏈表的頭節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)是 null浸颓。
這個題看起來很簡單,但是很多時候产上,在我一段時間不接觸這個題之后再來做的時候晋涣,還是會出錯。為了把這個題徹徹底底地梳理清楚算吩,還是畫圖來處理的比較好佃扼。
問題的核心,在于幾個指針的移動過程压昼,梳理清楚循環(huán)過程中指針的移動,這個題就理清楚了匠题。
/**
* 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)體前韭山,聲明了一個值為 null 的前驅(qū)節(jié)點(diǎn)冷溃,這個是符合場景的,因?yàn)槌跏兼湵淼念^節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)就是 null续搀。
初始化
-
循環(huán)體第一步禁舷,聲明了一個新的指針毅往,保存的是當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)引用攀唯。
step1 - 循環(huán)體第二步侯嘀,將當(dāng)前節(jié)點(diǎn)的后繼節(jié)點(diǎn)引用修改為指向前驅(qū)節(jié)點(diǎn)。這里可以看到第一步代碼的作用了吠谢,只有先用指針保留對原來的后繼節(jié)點(diǎn)的引用诗茎,在修改了當(dāng)前節(jié)點(diǎn)的后繼引用指向之后敢订,才能保持對鏈表后半段的控制。沒有這個 item 指針楚午,我們就無法繼續(xù)控制斷開連接引用的兩段鏈表醒叁。
step2 - 第三步把沼,將前驅(qū)節(jié)點(diǎn)指針指向修改為指向當(dāng)前節(jié)點(diǎn)。原來的鏈表頭節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)是 null饮睬,但是頭節(jié)點(diǎn)之后的節(jié)點(diǎn),它們的前驅(qū)節(jié)點(diǎn)就都不是 null 了割去,所以需要在循環(huán)體內(nèi)不斷更新這個前驅(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