Categories
學習筆記

Linked-list Reverse的思路

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。

  1. //linked-list的原型
  2. struct node{
  3.      value;
  4.      *next;
  5. }
  6.  
  7. typedef struct node xnode;
  8. typedef xnode *xnodeptr; //简化指向pointer的pointer
  9.  
  10. void reversenode(xnodeptr *sPtr){
  11.  
  12.      xnodeptr tmp;
  13.      xnodeptr previous=NULL;
  14.      xnodeptr current=*sPtr;
  15.  
  16.      while (current!=NULL){
  17.            tmp = current->next;
  18.            current->next = previous;
  19.            previous = current;
  20.            current = tmp;
  21.      }
  22.  
  23.      *sPtr = previous; 
  24.      //最后收集好的pointer是previous 别忘了丢回给原本的*sPtr。
  25. }

大功告成!哈哈

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.