单链表的逆置

单链表的逆置的实现:

 

(1)算法

struct link
{
  int data;
  struct link *next;
};

link reverse(link x)
{
  if( NULL==x )
    return NULL;
  
  link t=NULL;
  link r=NULL, y=x;  //(0)
  while(y!=NULL)
  {
    t = y->next;   //(1)
    y->next = r;   //(2)
    r = y;         //(3) 
    y = t;         //(4)
   }

  return r;     //返回逆置后的链表
}

(二)原理
(0)(1)(2)(3)(4)分别对应以上程序的各序号
第一次while循环
-------------------------------------------
(0) r=NULL, y=x

r=NULL    a    --->    b     --->   c   --->  d --> NULL
          |(0)            
          y            

-------------------------------------------
(1) t =y->next

r=NULL    a    --->    b     --->   c   --->  d --> NULL
          |(0)         | (1)  
          y            t 


--------------------------------------------
(2) y->next = r
              
a    --->  NULL            b     --->   c   --->  d --> NULL
|(0)   (2)  |              | (1)  
y           r              t 
 
---------------------------------------------       
(3) r = y    
          
a    --->  NULL            b     --->   c   --->  d --> NULL
|(0)   (2)                 | (1)  
y                          t 
|(3)
r

--------------------------------------------- 
(4) y = t
              
a    --->  NULL            b     --->   c   --->  d --> NULL
|(0)   (2)                | (1)  
|                         t 
|(3)                      | (4)
r                         y


第二次while循环(并对上面进行整理)
--------------------------------------------- 
(1) t = y->next
              
a    --->  NULL            b     --->   c   --->  d --> NULL
|                          |            |(1)
r                          y            t
                         
--------------------------------------------- 
(2) y->next = r
              
b  --->  a    --->  NULL         c   --->  d --> NULL
|  (2)   |                       |(1)
y        r                       t

--------------------------------------------- 
(3) r = y
              
b  --->  a    --->  NULL         c   --->  d --> NULL
|  (2)                           |(1)
y                                t
|  (3)
r

--------------------------------------------- 
(4) y = t
              
b  --->  a    --->  NULL         c   --->  d --> NULL
|  (2)                           |(1)
|                                t
|  (3)                           |(4)
r                                y


第三个循环 (并对上面的进行整理)
--------------------------------------------- 
(1) t = y->next
              
b  --->  a    --->  NULL         c   --->  d --> NULL
|                                |         |(1)
r                                y         t

以后的与第二次循环同, 最终可得:
              
d ---> c  ---> b  --->  a    --->  NULL