C++中经典的单向链表反转

1 struct linka {
2 int data;
3 linka* next;
4 };
5 void reverse(linka*& head) {
6 if(head ==NULL)
7     return;
8 linka *pre, *cur, *ne;
9 pre=head;
10 cur=head->next;
11 while(cur)
12 {
13    ne = cur->next;
14    cur->next = pre;
15    pre = cur;
16    cur = ne;
17 }
18 head->next = NULL;
19 head = pre;
20 }
其中比较难理解的是linka*& head，传入的其实就是linka *的类型就可以了，linka *是表示linka类型的指针，&表示head的地址，也就是linka的指针www.zzzyk.com

另外需要熟悉的是head->next，其实有点像C#中的head.Next，就是structure中的一个属性.

首先定义3个指针，分别是前中后，然后当中间那个指针非空，就是当前不是空，就做循环里的事情

注意的是这个算法里面next是在循环里面赋值的

每次循环都把current指向previous了，然后大家都往后移一个，next=current->next必须在current改变方向之前做，否则改变了方向之后current的next就变成previous了。

最后跳出循环之后，将header的next首先置空，因为head变成了最后一个node了。然后head就变成了previous，因为当时 current和next都为NULL了，只有previous为最后一个节点（或者说这时候应该是第一个非空节点，也就是head）

终于把整个算法理解了一遍，最后想想其实挺简单，但是能用c++写出来也不太容易，特别是在面试的时候。

再增加一个递归的单链表反转的方法：

1 static link ReverseLink3(link pNode)   // using recursion
2         {
3             if (pNode.next == null)
4                 return pNode;
5             link pNext = pNode.next;
6             link head = ReverseLink3(pNext);
7             pNext.next = pNode;
8             pNode.next = null;
9             return head;
10         }

补充：软件开发 , C++ ,