題目描述：給出單向鏈表的頭節(jié)點l望伦，如何只遍歷一次就將鏈表中的所有元素倒轉(zhuǎn)林说。
算法描述：
首先給出單向鏈表的結(jié)構(gòu)
struct LinkList {
int data;
LinkList *next;
};
遍歷一次鏈表，對于每一個節(jié)點p屯伞，記錄p的前驅(qū)pre腿箩，將p節(jié)點的后繼（即next域）指向pre，即可完成倒轉(zhuǎn)劣摇。
算法步驟:
1珠移、設(shè)p節(jié)點指向頭指針l的下一個節(jié)點（即指向第一個元素），pre設(shè)為NULL
2末融、若p的下一個節(jié)點為空钧惧，跳到4，否則跳到3
3勾习、將q指向p的下一個節(jié)點浓瞪，將p的next域指向pre節(jié)點，將pre指向p節(jié)點巧婶，將p指向q節(jié)點乾颁，跳到2
4、將p的next域指向pre節(jié)點
5艺栈、結(jié)束
實現(xiàn)：
p = l->next;
pre = NULL;
while (p->next != NULL) {
q = p->next;
p->next = pre;
pre = p;
p = q;
}
p->next = pre;
return p;
算法說明：
顯然英岭，這道題目如果通過記錄data域來實現(xiàn)調(diào)轉(zhuǎn)，算法復(fù)雜度在O(n^2)級湿右，因為在不使用輔助數(shù)組的情況下诅妹，每次顛倒需要從頭節(jié)點以O(shè)(n)的時間復(fù)雜度找到需要顛倒的節(jié)點。所以我們不妨換一個想法毅人，從鏈表的next域下手吭狡。很容易想到，如果我們將每個節(jié)點的next域都指向它的前驅(qū)而不是后繼堰塌，就可實現(xiàn)調(diào)轉(zhuǎn)赵刑。我們不妨具體舉例說明。
1->2->3->4->5
假設(shè)前兩個節(jié)點已經(jīng)完成倒轉(zhuǎn)场刑，那么鏈表就可以表示成:
1<-2
3->4->5
可以看出般此，鏈表變?yōu)榱藘刹糠烛秸健＿@時我們需要一個指針記錄3的當(dāng)前后繼（也就是4），以完成后續(xù)遍歷铐懊，之后將3的next域指向2邀桑，并記錄3的位置（以便4指向3），即可完成前3個節(jié)點的倒轉(zhuǎn)科乎。
