要求很簡單染厅，輸入一個鏈表，反轉(zhuǎn)鏈表后脓杉，輸出新鏈表的表頭糟秘。
??反轉(zhuǎn)鏈表是有2種方法(遞歸法，遍歷法)實現(xiàn)的球散，面試官最愛考察的算法無非是斐波那契數(shù)列和單鏈表反轉(zhuǎn)尿赚，遞歸方法實現(xiàn)鏈表反轉(zhuǎn)比較優(yōu)雅，但是對于不了解遞歸的同學(xué)來說還是有理解難度的蕉堰。
遞歸法
總體來說凌净，遞歸法是從最后一個Node開始，在彈棧的過程中將指針順序置換的屋讶。
遞歸法實現(xiàn)圖
為了方便理解冰寻，我們以 1->2->3->4這個鏈表來做演示。輸出的效果是4->3->2->1
首先定義Node：
public static class Node {
public int value;
public Node next;
public Node(int data) {
this.value = data;
}
}
反轉(zhuǎn)方法如下：
public Node reverse(Node head) {
if (head == null || head.next == null)
return head;
Node temp = head.next;
Node newHead = reverse(head.next);
temp.next = head;
head.next = null;
return newHead;
}
遞歸實質(zhì)上就是系統(tǒng)幫你壓棧的過程皿渗，系統(tǒng)在壓棧的時候會保留現(xiàn)場斩芭。
我們來看是怎樣的一個遞歸過程：1->2->3->4
- 程序到達(dá)Node newHead = reverse(head.next);時進(jìn)入遞歸
- 我們假設(shè)此時遞歸到了3結(jié)點轻腺，此時head=3結(jié)點，temp=3結(jié)點.next(實際上是4結(jié)點)
- 執(zhí)行Node newHead = reverse(head.next);傳入的head.next是4結(jié)點划乖，返回的newHead是4結(jié)點贬养。
- 接下來就是彈棧過程了
- 程序繼續(xù)執(zhí)行 temp.next = head就相當(dāng)于4->3
- head.next = null 即把 3結(jié)點指向4結(jié)點的指針斷掉。
- 返回新鏈表的頭結(jié)點newHead
注意：當(dāng)retuen后琴庵，系統(tǒng)會恢復(fù)2結(jié)點壓棧時的現(xiàn)場误算，此時的head=2結(jié)點；temp=2結(jié)點.next(3結(jié)點)迷殿，再進(jìn)行上述的操作儿礼。最后完成整個鏈表的翻轉(zhuǎn)。
遍歷法
遍歷法就是在鏈表遍歷的過程中將指針順序置換
遍歷法實現(xiàn)圖
先上代碼：
public static Node reverseList(Node node) {
Node pre = null;
Node next = null;
while (node != null) {
next = node.next;
node.next = pre;
pre = node;
node = next;
}
return pre;
}
依舊是1->2->3->4
- 準(zhǔn)備兩個空結(jié)點 pre用來保存先前結(jié)點庆寺、next用來做臨時變量
- 在頭結(jié)點node遍歷的時候此時為1結(jié)點
- next = 1結(jié)點.next(2結(jié)點)
- 1結(jié)點.next=pre(null)
- pre = 1結(jié)點
- node = 2結(jié)點
- 進(jìn)行下一次循環(huán)node=2結(jié)點
- next = 2結(jié)點.next(3結(jié)點)
- 2結(jié)點.next=pre(1結(jié)點)=>即完成2->1
- pre = 2結(jié)點
- node = 3結(jié)點
- 進(jìn)行循環(huán)...
