单链表反转 指针坑

单链表反转 指针坑 

当我看到单链表反转这题目时，感觉这么简单啊。事实很多坑，一不小心就跳进去了。到现在我都记不清跳了多少坑。

写代码时不是死循环就是就是丢数据。 这 其实本质上是 指针的坑。一不留神就over了。

 

因为前面已经实现过各种列表的插入。

1、我首先想到的是从A链表中取出数据再生成一个新的链表B，从表头脑插入这样成了链表的反转了。

就顺手写了下面代码[1],运行进入死循环。

出现错误的原因:

假设，有 A->B->C->D->E这样一个链表

for循环中第一个head默认是A，h->next(A的指向的一个元素)是B。当然调用insert时 head作为参数传入。在insert方法里面参数node 等价于head。 

所以node->next=head  <=> head->next =head; 这样就造成死循环了。

 

又想当然的在reverse中定义了pre [2].照样出错。原因跟上面是一样的，head的next指向了自己。

还犯了一个错误就是单链表最后一个next没有赋值NULL,还有各种尝试就不在一一列举了，总之都是忽视指针指向错误。

 

[1]reverse代码片段
 90 void reverse(void)
 91 {
 92     for(; head; head = head->next){
 93         insert(head);
 94     }
 95 }  
[2]
 90 void reverse(void)
 91 {
 92     link pre = malloc(sizeof pre);
 93     pre = head;
 94     for(; pre; pre = pre->next){
 95         printf("%c\n", pre->element);                                                                      
 96         insert(pre);
 97     }
 98 }
     static link head;
 66 void insert(link node)   
 67 {
 68     if(head==NULL){      
 69        tail = node;      
 70     }
 71     node->next = head;   
 72     head = node;
 73 }
 74

1、重新构造一个head,当同时记住head的下一个元素,并把head的next设置为NULL.

循环遍历前，先取的head->next的对称赋值给curn。curn用来记录遍历位置，并把head的next设置为NULL. head会变成尾，这样保证尾节点指向NULL.

方法1、
 void reverse(void)
163 {
164     link curn;
165     link temp;
166     if(head == NULL){
167         return;
168     }
169     curn = head->next,
170     head->next = NULL;
171     while(curn != NULL){
172         temp = curn;        //保存当前节点
173         curn = curn->next;  //改变curb指向下一个节点                                                                            
174         temp->next = head; // 把head赋值给temp指向的节点
175         head = temp;  //最后把temp赋值给head
176     }
177     return;
178 } 

方法2、
这里实现使用把curn指向的下一个节点保存起来,curn指向的下一个节点改为指向head。然后把curn赋值给head，并把temp赋值给curn
142 void reverse(void)
143 {
144     link curn;
145     link temp;
146     if(head == NULL){
147         return;
148     }
149     curn = head->next,
150     head->next = NULL;
151     while(curn != NULL){
152         temp = curn->next;
153         curn->next = head;
154         head = curn;
155         curn = temp;                                                                                       
156     }
157     return;
158 }  
159　
方法3
 1、如果head 或head->next为空直接返回
 2、进入循环前需要先把pre赋值为NULL,防止出现链表尾元素为非空
 99 void reverse(void)
100 {
101     link pre, cn;
102     if(head==NULL || head->next==NULL){
103         return;
104     }                                                                                                       
106     pre = NULL;             
107     while(head->next){     在循环中pre保存了每次遍历生成的新链表关系
108         cn = head->next;   //保存 当前head节点指向的节点head->next
109         head->next = pre;  //更改head指向 前一个pre保存的节点或NULL，
110         pre = head;           //然后pre在保存当前head
111         head = cn;           //最后从cn中循环中第一个语句保存的heade 指向的节点赋值给head
112     }
113     head->next = pre ;    //退出循环后，head已经是最后一个节点，只需把head 的next指向pre既可
114
115     return;
116 }