单链表反转

反转链表，又可以称为翻转或逆置链表，它们表达的是同一个意思。以图 1 所示的链表为例：

经过反转（翻转，逆置）后得到新的链表（图2）：

迭代反转法

该算法的实现思想非常的直接，就是从当前链表的首元节点开始，一直遍历至节点的最后一个节点，这期间会逐个改变所遍历到的节点的指针域，令其指向前一个节点。

具体的实现方法也很简单：借助3个指针即可，以图1中建立的链表为例，首先我们定义 3 个指针并分别命名为 beg、mid、end。它们的初始指向如图 3 所示：

在上图的基础上，遍历链表的过程就等价为：3 个指针每次各向后移动一个节点，直至 mid 指向链表中最后一个节点（此时 end 为 NULL ）。需要注意的是，这 3 个指针每移动之前，都需要做一步操作，即改变 mid 所指节点的指针域，另其指向和 beg 相同。

1. 在图 3 的基础上，我们先改变 mid 所指节点的指针域指向，另其和 beg 相同（即改为 NULL），然后再将 3 个指针整体各向后移动一个节点。整个过程如图 4 所示：

2. 在图 4 基础上，先改变 mid 所指节点的指针域指向，另其和 beg 相同（指向节点 1 ），再将 3 个指针整体各向后移动一个节点。整个过程如图 5 所示：

3. 在图 5 基础上，先改变 mid 所指节点的指针域指向，另其和 beg 相同（指向节点 2 ），再将 3 个指针整体各向后移动一个节点。整个过程如图 6 所示：

4. 图 6 中，虽然 mid 指向了原链表最后一个节点，但显然整个反转的操作还差一步，即需要最后修改一次 mid 所指节点的指针域指向，另其和 beg 相同（指向节点 3）。如图 7 所示：

注意：这里只需要改变mid所指节点的指向即可，不用修改3个指针的指向。

5. 最后只需改变 head 头指针的指向，另其和 mid 同向，就实现了链表的反转。

typedef struct Link {
	char elem;
	struct Link* next;
} link;

// 迭代反转法实现列表翻转
link* iteration_reverse(link* head)
{
	if(head==NULL || head->next==NULL)
	{
		//只有一个节点无需反转 
		return head;
	}
	
	link* beg=NULL;
	link* mid=head;
	link* end=head->next;
	
	//遍历
	while(1)
	{
		//修改mid所指节点的指向
		mid->next=beg;
		//判断end是否为空，如果为空，则代表已经遍历到最后一个节点，退出循环
		if(end==NULL)
		{
			break; 
		} 
		
		//三个指针向后移
		beg=mid;
		mid=end;
		end=end->next; 
	} 
	
	//整体修改完后需要修改头指针指向
	head=mid;
	return head; 
}