一、問(wèn)題描述
初始狀態(tài)：
目標(biāo)狀態(tài)：
二、遞歸法
反轉(zhuǎn)單向鏈表
思路：先從前面遞歸到后面，使得每次遞歸時(shí)的指針指向當(dāng)前結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)；執(zhí)行時(shí)從最后面的兩個(gè)結(jié)點(diǎn)開(kāi)始反轉(zhuǎn)，依次向前，將后一個(gè)鏈表結(jié)點(diǎn)指向前一個(gè)結(jié)點(diǎn)，注意每次反轉(zhuǎn)后要將原鏈表中前一個(gè)結(jié)點(diǎn)的指針域置空，表示將原鏈表中前一個(gè)結(jié)點(diǎn)指向后一個(gè)結(jié)點(diǎn)的指向關(guān)系斷開(kāi)。
ListNode * ReverseList(ListNode * head)
{
//遞歸終止條件：找到鏈表最后一個(gè)結(jié)點(diǎn)
if (head == NULL || head->next == NULL)
return head;
else
{
ListNode * newhead = ReverseList(head->next);//先反轉(zhuǎn)后面的鏈表，從最后面的兩個(gè)結(jié)點(diǎn)開(kāi)始反轉(zhuǎn)，依次向前
head->next->next = head;//將后一個(gè)鏈表結(jié)點(diǎn)指向前一個(gè)結(jié)點(diǎn)
head->next = NULL;//將原鏈表中前一個(gè)結(jié)點(diǎn)指向后一個(gè)結(jié)點(diǎn)的指向關(guān)系斷開(kāi)
return newhead;
}
}
理解：假如要當(dāng)前要反轉(zhuǎn)1->2，head永遠(yuǎn)指向結(jié)點(diǎn)1，而newhead是個(gè)固定值指向結(jié)點(diǎn)5.
三、非遞歸法
單鏈表反轉(zhuǎn)的遞歸方法和非遞歸方法
代碼一：
思路：利用兩個(gè)結(jié)點(diǎn)指針和一個(gè)頭結(jié)點(diǎn)指針head(用來(lái)記錄當(dāng)前結(jié)點(diǎn)的位置)，分別指向前一個(gè)結(jié)點(diǎn)、當(dāng)前結(jié)點(diǎn)和下一個(gè)結(jié)點(diǎn)，每次循環(huán)讓當(dāng)前結(jié)點(diǎn)的指針域指向前一個(gè)結(jié)點(diǎn)即可；每一次翻轉(zhuǎn)前需要先保存當(dāng)前節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，再進(jìn)行翻轉(zhuǎn)，然后更新另外兩個(gè)結(jié)點(diǎn)指針。
public ListNode reverseList(ListNode head) {
ListNode next = null;
ListNode pre = null
while (head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
理解：假如1->2，則next指向2，且每次更新為2指向的結(jié)點(diǎn)；pre指向1，且每次更新為1指向的結(jié)點(diǎn)。
代碼二
ListNode* reverseList2(ListNode* head) {
if (head == NULL || head->next == NULL)
return head;
ListNode* prev = head;
ListNode* cur = head->next;
ListNode* temp = head->next->next;
while (cur){
temp = cur->next; //temp作為中間節(jié)點(diǎn)，記錄當(dāng)前結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的位置
cur->next = prev; //當(dāng)前結(jié)點(diǎn)指向前一個(gè)節(jié)點(diǎn)
prev = cur; //指針后移
cur = temp; //指針后移，處理下一個(gè)節(jié)點(diǎn)
}
head->next = NULL; //while結(jié)束后，將翻轉(zhuǎn)后的最后一個(gè)節(jié)點(diǎn)（即翻轉(zhuǎn)前的第一個(gè)結(jié)點(diǎn)head）的鏈域置為NULL
return prev;
}
代碼二與代碼一思路一樣！
