程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> C++中經典的單向鏈表反轉

C++中經典的單向鏈表反轉

編輯:C++入門知識

 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         }

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved