Linked-list Reverse的思路:
比如原本是這樣 1 2 3 4 5 |
第一次之后变成 2 3 4 5 | 1
第二次之后变成 3 4 5 | 2 1
第三次之后变成 4 5 | 3 2 1
第四次之后变成 5 | 4 3 2 1
第五次之后变成 | 5 4 3 2 1
Linked-list里的一个pointer是一路走到底不能回头的
所以你要reverse的话一定有一个暂存的pointer
保存这个pointer以后的东西 我们就叫他tmp吧
再来你还需要一个新的pointer来存你的新linked-list
暂且叫他previous吧 至于为什么你之后就知道了
1)刚说了要写暂存
tmp = current->next
2)我们要做的就是把以前的previous接在现在这个current的后面去
(看第二次的时候 2是current 1是previous 第三次的时候3是current 21是previous 以此类推)
current->next = previous
3)然后把现在的current设为previous(准备给下一次用)
previous = current
4)最后一步把暂存的tmp丢回去给current(把暂存的放回去 准备下一次运行)
current = tmp
分析完毕之后开始写function。
- //linked-list的原型
- struct node{
- value;
- *next;
- }
- typedef struct node xnode;
- typedef xnode *xnodeptr; //简化指向pointer的pointer
- void reversenode(xnodeptr *sPtr){
- xnodeptr tmp;
- xnodeptr previous=NULL;
- xnodeptr current=*sPtr;
- while (current!=NULL){
- tmp = current->next;
- current->next = previous;
- previous = current;
- current = tmp;
- }
- *sPtr = previous;
- //最后收集好的pointer是previous 别忘了丢回给原本的*sPtr。
- }
大功告成!哈哈