算法实现：倒转单链表

本文的copyleft归[e-mail]所有，使用GPL发布，可以自由拷贝，转载。但转载请保持文档的完整性，注明原作者及原链接，严禁用于任何商业用途。
作者：[e-mail]
博客：linuxfocus.blog.chinaunix.net

这又是一道比较俗的题目，但是却经常可以见到。今天想到这道题，虽然知道如何解决，但是把代码完全写好，并调试验证，居然也花了20分钟。看来真的需要好好巩固巩固这些基础知识和算法了。

好，下面回到正题。

单链表的节点，只有一个指针指向下一个节点，那么如果要倒转单链表，如何解决呢？

下面的解决方法，即以swap两个变量的思想，对于链表来说，即使用三个临时指针，来交换指针地址，实现一次遍历单链表，即完成单链表倒转的工作。

struct list_node {
    struct list_node *next;
    void *data;
};

/*
该函数用于倒转单链表
参数：head为输入的单链表头指针；
返回值为：倒转后的单链表的头指针；
*/
struct list_node *reverse_list(struct list_node *head)
{
    /* 检查是否为指针是否有效 */
    if (!head) {
        return NULL;
    }

     /* 初始化三个临时指针 */

    struct list_node *p1, *p2, *p3;
    p1 = head;
    p2 = p3 = NULL;

     /* 遍历该单链表，并利用三个临时指针，对单链表的节点的next进行交换 */

    while (p1->next) {
        p2 = p1->next;
        p1->next = p3;

        if (!p2->next) {
            p2->next = p1;
            return p2;
        }
        p3 = p2->next;
        p2->next = p1;

        if (!p3->next) {
            p3->next = p2;
            return p3;
        }
        p1 = p3->next;
        p3->next = p2;
    }
    p1->next = p3;

    return p1;
}

这个函数的代码我写得一般，感觉好像还可以把代码再优化一下，更简洁一些。我就不做这个工作了，抛砖引玉了，望大家指正。