鏈表逆序是個(gè)很基礎(chǔ)的算法，考察的是指針操作和基本數(shù)據(jù)結(jié)構(gòu)携取。常規(guī)的寫(xiě)法當(dāng)然是OK的纳令，不過(guò)要是還會(huì)寫(xiě)出一個(gè)遞歸的鏈表逆序算法，那別人肯定要給你點(diǎn)個(gè)贊了进栽。
1 問(wèn)題描述
給定一個(gè)鏈表德挣，請(qǐng)將其逆序。即如果鏈表原來(lái)為1->2->3->4->5->null快毛，逆序后為5->4->3->2->1->null.
2 常規(guī)寫(xiě)法(迭代)
迭代算法效率較高格嗅，但是代碼比遞歸算法略長(zhǎng)。遞歸算法雖然代碼量更少唠帝，但是難度也稍大屯掖，不細(xì)心容易寫(xiě)錯(cuò)。迭代算法的思想就是遍歷鏈表襟衰，改變鏈表節(jié)點(diǎn)next指向贴铜，遍歷完成，鏈表逆序也就完成了瀑晒。代碼如下：
struct node {
int data;
struct node* next;
};
typedef struct node* pNode;
pNode reverse(pNode head)
{
pNode current = head;
pNode next = NULL, result = NULL;
while (current != NULL) {
next = current->next;
current->next = result;
result = current;
current = next;
}
return result;
}
如果不返回值绍坝，可以傳遞參數(shù)改為指針的指針，直接修改鏈表的頭結(jié)點(diǎn)值（如果在C++中直接傳遞引用更方便）苔悦，可以寫(xiě)出下面的代碼：
void reverse(pNode* headRef)
{
pNode current = *headRef;
pNode next = NULL, result = NULL;
while (current != NULL) {
next = current->next;
current->next = result;
result = current;
current = next;
}
*headRef = result;
}
3 進(jìn)階寫(xiě)法(遞歸)
遞歸寫(xiě)法的實(shí)現(xiàn)原理：假定原鏈表為1轩褐，2，3间坐，4灾挨，則先逆序后面的2邑退，3，4變?yōu)?劳澄，3地技，2，然后將節(jié)點(diǎn)1鏈接到已經(jīng)逆序的4秒拔，3莫矗，2后面，形成4砂缩，3作谚，2，1庵芭，完成整個(gè)鏈表的逆序妹懒。代碼如下：
void reverseRecur(pNode* headRef)
{
if (*headRef == NULL) return;
pNode first, rest;
first = *headRef;
rest = first->next;
if (rest == NULL) return;
reverseRecur(&rest);
first->next->next = first; //注意這里不要錯(cuò)寫(xiě)成rest->next = first噢，請(qǐng)想想指針的指向双吆。
first->next = NULL;
*headRef = rest; //更新頭結(jié)點(diǎn)
}
如果使用C++的引用類(lèi)型眨唬，代碼會(huì)稍顯簡(jiǎn)單點(diǎn)，代碼如下：
void reverseRecur(pNode& p)
{
if (!p) return;
pNode rest = p->next;
if (!rest) return;
reverseRecur(rest);
p->next->next = p;
p->next = NULL;
p = rest;
}
參考資料
leetcode的鏈表某一節(jié)的題目好乐，具體鏈接找不到了匾竿，請(qǐng)見(jiàn)諒
