单链表的反转(1)

通过前面章节的学习，读者已经对单链表以及它的用法有了一个完整的了解。在此基础上，本节再带领大家研究一个和单链表有关的问题，即如何实现单链表的反转。

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

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

通过对比图 1 和 图 2 中的链表不难得知，所谓反转链表，就是将链表整体“反过来”，将头变成尾、尾变成头。那么，如何实现链表的反转呢？

常用的实现方案有 4 种，这里分别将它们称为迭代反转法、递归反转法、就地逆置法和头插法。值得一提的是，递归反转法更适用于反转不带头节点的链表；其它 3 种方法既能反转不带头节点的链表，也能反转带头节点的链表。

迭代反转链表

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

这里使用的是有头节点的链表，创建三个指针：

link* temp, * front, * back; // front表示temp节点之前的指针，back表示temp节点之后的指针
front = back = NULL; // 初始化指针
temp = l;

首先将*temp指针指向头节点*l，判断是否有temp->next，然后temp=temp->next，将temp指针向后移动

if (temp->next)
{
    temp = temp->next;        
}

当*temp指向首元节点之后，就可以开始while循环了：

while (temp->next) // 如果temp还存在下个节点
{
    back = temp->next; // 将back节点向后移动
    temp->next = front; // 将temp节点的next重新链接为它之前的节点
    front = temp; // 将front节点向后移动
    temp = back; // 将temp节点(也就是当前节点)向后移动
}

通过back, temp, front三个指针的向后移动，达到向后迭代的效果。

当temp->next为空时停止循环：

temp->next = front; // 将最后一个节点的next指针指向前一个节点

将头节点的指针指向最后一个节点，就是temp：

注意，最开始的节点在front = NULL时就已经指向front了，上面几张图因为那时头节点还是指向它，所以没表示出来。

l->next = temp;
return l; // 返回链表

完整代码

// 反转链表
link* invertLink(link* l) {
    link* temp, * front, * back;
    front = back = NULL;
    temp = l; // 将temp指针指向头结点
    if (temp->next)
    {
        temp = temp->next; // 将temp指向首元节点        
    }
    while (temp->next) // 开始while循环，直到temp没有下个节点
    {
        back = temp->next;
        temp->next = front;
        front = temp;
        temp = back;        
    }
    temp->next = front;
    l->next = temp;
    return l;
}