1 struct linka {
2 int data;
3 linka* next;
4 };
5 void reverse(linka*& head) {
6 if(head ==NULL)
7 return;
8 linka *pre, *cur, *ne;
9 pre=head;
10 cur=head->next;
11 while(cur)
12 {
13 ne = cur->next;
14 cur->next = pre;
15 pre = cur;
16 cur = ne;
17 }
18 head->next = NULL;
19 head = pre;
20 }
其中比較難理解的是linka*& head,傳入的其實就是linka *的類型就可以了,linka *是表示linka類型的指針,&表示head的地址,也就是linka的指針www.2cto.com
另外需要熟悉的是head->next,其實有點像C#中的head.Next,就是structure中的一個屬性.
首先定義3個指針,分別是前中後,然後當中間那個指針非空,就是當前不是空,就做循環裡的事情
注意的是這個算法裡面next是在循環裡面賦值的
每次循環都把current指向previous了,然後大家都往後移一個,next=current->next必須在current改變方向之前做,否則改變了方向之後current的next就變成previous了。
最後跳出循環之後,將header的next首先置空,因為head變成了最後一個node了。然後head就變成了previous,因為當時 current和next都為NULL了,只有previous為最後一個節點(或者說這時候應該是第一個非空節點,也就是head)
終於把整個算法理解了一遍,最後想想其實挺簡單,但是能用c++寫出來也不太容易,特別是在面試的時候。
再增加一個遞歸的單鏈表反轉的方法:
1 static link ReverseLink3(link pNode) // using recursion
2 {
3 if (pNode.next == null)
4 return pNode;
5 link pNext = pNode.next;
6 link head = ReverseLink3(pNext);
7 pNext.next = pNode;
8 pNode.next = null;
9 return head;
10 }