題目概述：
? ? ? ? Reverse a singly linked list.
? ? ? ? 翻轉(zhuǎn)一個(gè)單鏈表，如：1->2 輸出 2->1；1->2->3 輸出3->2->1。

題目解析：
? ? ? ? 本人真的比較笨啊！首先想到的方法就是通過判斷鏈尾是否存在，再新建一個(gè)鏈表，每次移動(dòng)head的鏈尾元素，并刪除head鏈表中的元素，一個(gè)字“蠢”，但好歹AC且鞏固了鏈表基礎(chǔ)知識。你可能遇見的錯(cuò)誤包括：
? ? ? ? 1.'ListNode' undeclared (first use in this function)
? ? ? ??nhead=(istNode*)malloc(sizeof(ListNode)); ? ?
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? =>
? ? ? ??nhead=(struct ListNode*)malloc(sizeof(struct ListNode));
? ? ? ? 2.Time Limit Exceeded
? ? ? ? 在鏈表遍歷尋找最后一個(gè)結(jié)點(diǎn)并插入新鏈表尾部中需要注意，建議的方法：
? ? ? ? q=head; while(q) {q=q->next;}
? ? ? ? p=(struct ListNode*)malloc(sizeof(struct ListNode));
? ? ? ? p->val=head->val; p->next=NULL; q=p; ? ? ??
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? =>
? ? ? ??q=head; while(q) {last=q; q=q->next;}?
? ? ? ? p=(struct ListNode*)malloc(sizeof(struct ListNode));
? ? ? ? p->val=head->val; p->next=NULL; last->next=p;
? ? ? ? 通過借助last變量更直觀，否則結(jié)果總是錯(cuò)誤。而且此時(shí)q為next指向NULL，如果用到q->next=p就會(huì)出現(xiàn)RE錯(cuò)誤，因?yàn)閝都為NULL，哪來的q->next。第二個(gè)錯(cuò)誤也可能是我個(gè)人的編程習(xí)慣吧！
? ? ? ? 第二種方法更為推薦——直接翻轉(zhuǎn)，還有一種遞歸方法自行提高。
? ? ? ? 如下圖所示，紅色表示初始鏈表存在4個(gè)值[1, 2, 3, 4]，藍(lán)色表示初始指針first指向第一個(gè)元素、second指向第二個(gè)元素(head->next)，third指向第三個(gè)元素；首先s->next=f斷開鏈表并翻轉(zhuǎn)指向第一個(gè)元素，同時(shí)f=s最后返回first。如果只有兩個(gè)元素[1, 2]則執(zhí)行"s->next=f; f=s;"后s=t=NULL返回f即可輸出[2, 1]。

我的代碼：
直接翻轉(zhuǎn)方法 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/ struct ListNode* reverseList(struct ListNode* head) {struct ListNode *first,*second,*third;if(head==NULL||head->next==NULL)return head;first = head;second = head->next;first->next = NULL;while(second!=NULL) { //注意while(second)不能執(zhí)行third = second->next;second->next = first;first = second;second = third;}return first; } "蠢"方法 /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*///個(gè)人思路:判斷鏈尾是否存在 翻轉(zhuǎn)到一個(gè)新鏈表 struct ListNode* reverseList(struct ListNode* head) {struct ListNode *nhead,*q,*p,*last,*nq,*np;int value;if(head==NULL||head->next==NULL)return head;q=head;nhead=NULL; //創(chuàng)建新表頭while(q->next) {//刪除最后一個(gè)鏈尾結(jié)點(diǎn)p=q;while(p->next) {last=p;p=p->next; }value=p->val;last->next=NULL;free(p);//插入行結(jié)點(diǎn)nq=nhead;while(nq) {last=nq;nq=nq->next;}if(nhead==NULL) { //創(chuàng)建表頭np=(struct ListNode*)malloc(sizeof(struct ListNode));np->val=value;nhead=np;nhead->next=NULL;}else { //插入結(jié)點(diǎn)np=(struct ListNode*)malloc(sizeof(struct ListNode));np->val=value;np->next=NULL;last->next=np;}//q結(jié)點(diǎn)循環(huán)前始終指向鏈表頭q=head;}//最后一個(gè)結(jié)點(diǎn)及頭結(jié)點(diǎn)headnq=nhead;while(nq) {last=nq; //使用nq=np總是報(bào)錯(cuò)WRnq=nq->next;}np=(struct ListNode*)malloc(sizeof(struct ListNode));np->val=head->val;np->next=NULL;last->next=np; //nq->next=np會(huì)報(bào)錯(cuò)RE 因?yàn)閚q此時(shí)為next及null,而nq->next更不知道在哪return nhead; }

(By:Eastmount 2015-9-14 晚上7點(diǎn) ?? http://blog.csdn.net/eastmount/ )

總結(jié)

以上是生活随笔為你收集整理的[LeetCode] Reverse Linked List I II - 链表翻转问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。