頭插法反轉(zhuǎn)鏈表
通過(guò)三指針涡贱，分別保存當(dāng)前節(jié)點(diǎn)指針巧勤，前節(jié)點(diǎn)指針，后節(jié)點(diǎn)指針票顾，每次移動(dòng)一位來(lái)反轉(zhuǎn)當(dāng)前節(jié)點(diǎn) next 指針的指向（將next指向pre)础浮。
public ListNode reverseList(ListNode head) {
ListNode cur = head;
ListNode pre = null;
ListNode next = null;
while(cur != null){
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
遞歸反轉(zhuǎn)鏈表
//迭代反轉(zhuǎn)法，head 為無(wú)頭節(jié)點(diǎn)鏈表的頭指針
link * iteration_reverse(link* head) {
if (head == NULL || head->next == NULL) {
return head;
}
else {
link * beg = NULL;
link * mid = head;
link * end = head->next;
//一直遍歷
while (1)
{
//修改 mid 所指節(jié)點(diǎn)的指向
mid->next = beg;
//此時(shí)判斷 end 是否為 NULL奠骄，如果成立則退出循環(huán)
if (end == NULL) {
break;
}
//整體向后移動(dòng) 3 個(gè)指針
beg = mid;
mid = end;
end = end->next;
}
//最后修改 head 頭指針的指向
head = mid;
return head;
}
}
迭代反轉(zhuǎn)鏈表
link* recursive_reverse(link* head) {
//遞歸的出口
if (head == NULL || head->next == NULL) // 空鏈或只有一個(gè)結(jié)點(diǎn)豆同，直接返回頭指針
{
return head;
}
else
{
//一直遞歸，找到鏈表中最后一個(gè)節(jié)點(diǎn)
link *new_head = recursive_reverse(head->next);
//當(dāng)逐層退出時(shí)含鳞，new_head 的指向都不變影锈，一直指向原鏈表中最后一個(gè)節(jié)點(diǎn)；
//遞歸每退出一層，函數(shù)中 head 指針的指向都會(huì)發(fā)生改變鸭廷，都指向上一個(gè)節(jié)點(diǎn)枣抱。
//每退出一層，都需要改變 head->next 節(jié)點(diǎn)指針域的指向辆床，同時(shí)令 head 所指節(jié)點(diǎn)的指針域?yàn)?NULL佳晶。
head->next->next = head;
head->next = NULL;
//每一層遞歸結(jié)束，都要將新的頭指針?lè)祷亟o上一層讼载。由此轿秧，即可保證整個(gè)遞歸過(guò)程中，能夠一直找得到新鏈表的表頭咨堤。
return new_head;
}
}
就地逆置法反轉(zhuǎn)鏈表
link * local_reverse(link * head) {
link * beg = NULL;
link * end = NULL;
if (head == NULL || head->next == NULL) {
return head;
}
beg = head;
end = head->next;
while (end != NULL) {
//將 end 從鏈表中摘除
beg->next = end->next;
//將 end 移動(dòng)至鏈表頭
end->next = head;
head = end;
//調(diào)整 end 的指向菇篡，另其指向 beg 后的一個(gè)節(jié)點(diǎn)，為反轉(zhuǎn)下一個(gè)節(jié)點(diǎn)做準(zhǔn)備
end = beg->next;
}
return head;
}
參考文章
當(dāng)前文章會(huì)將用java代碼實(shí)現(xiàn)全部一喘，當(dāng)前還未完成驱还，處于完善階段，參考文章：http://c.biancheng.net/view/8105.html
