|
鏈表反轉(zhuǎn)
1.鏈表有兩種，一是帶頭結(jié)點的：頭結(jié)點存儲長度信息，頭結(jié)點的next指向第一個實際節(jié)點；二是不帶頭結(jié)點的，頭結(jié)點即第一個節(jié)點。這里使用帶頭結(jié)點的鏈表。
2.需要三個指針，記錄當前節(jié)點（反轉(zhuǎn)用）、前一個節(jié)點、后一個節(jié)點（反轉(zhuǎn)之后前進用）。
測試的時候，在創(chuàng)建鏈表的時候，注意實際的new這個節(jié)點。
還要注意鏈表為空的情況。
- /*
- 鏈表
- 1.帶頭結(jié)點的：head里面存放鏈表長度（或其他信息），head->next指向第一個實際節(jié)點；
- 2.不帶頭結(jié)點的：head即第一個實際節(jié)點
- */
-
- typedef struct Node
- {
- int data;
- Node * next;
- };
-
- void reverseList(Node *head)
- {
- if ((head==NULL)||((head->next)==NULL)) return ; //如果head為空，或者頭結(jié)點指向空節(jié)點（鏈表長度為0），則退出。
-
- Node *pre,*cur,*next; //cur 記錄當前位置，pre記錄上一個位置，為cur->next的值；next記錄下一個位置，反轉(zhuǎn)后cur不等于cur->next
-
- cur=head->next;
- pre=NULL; //逆轉(zhuǎn)之后，頭結(jié)點變?yōu)槲补?jié)點，其next為Null
-
- while (cur!=NULL)
- {
- next=cur->next; //反轉(zhuǎn)后不能再用cur->next，所以先記錄下這個節(jié)點
- cur->next=pre;
- pre=cur;
- cur=next;
- }
-
- head->next=pre; //cur已經(jīng)為空，所以pre為尾節(jié)點。head->next指向它。
-
- return ;
- }
|
