反转单链表

第一次听到这个题目的时候，是在某公司的面试时。很遗憾，我当时没有做出来。不
久后，我把这个事就给忘了，直到在另一家公司面试。还好，当时面试官给了我足够
的时间和提示，我才用丑陋的代码将这个问题解决。现在，是时候总结一下了。

首先，我们定义一个节点：

typedef struct node {
    struct node *next;
} Node;

这个 Node 就是我们的单链表的节点，我们可以在次节点的内部嵌入数据，也可将此
节点嵌入到其他结构体中，构成支持其他结构体的骨架（看考linux代码树中的
struct list_head 结构体）。但将此节点用来干什么不是我们讨论的重点，我们关心
的只是如何实现反转单链表这个功能。

方法一：

数据结构以及对其的操作要求我们有一定的空间想想能力。最直观的一种情况就是，
从原始的表头到表尾，依次反转 next 指针：

Node *reverse(Node *Head)
{
    Node *p1, *p2, *p3;

    if (Head == NULL || Head->next == NULL)
        return Head;   // 如果Head为空，或只有一个节点，直接返回 Head

    p1 = Head;
    p2 = p1->next;     // 标定 p1 p2

    p1->next = NULL;
    while (p2 != NULL) {
        p3 = p2->next; // 更新 p3，以记录 p2->next
        p2->next = p1;
        p1 = p2;
        p2 = p3;       // 蠕虫式爬行
    }

    return p1;
}
    

上面的方法中，利用了三个指针 p1, p2 和 p3 来指示我们所要处理的位置，其中关
键的是对于 p3 的更新。因为一旦 p2->next 被更改为指向 p1，则不能找到下一个节
点的位置。因此需要先利用 p3 = p2->next 将下一节点位置记录下来，之后再更新
p2->next 。

方法二：

方法一其实就是一种迭代的方法。下面，我们讨论使用递归来解决这个问题。

Node *reverse_recur(Node *Head)
{
    Node *new_head;
    if (Head == NULL || Head->next == NULL)
        return Head;

    new_head = reverse_recur(Head->next);

    Head->next->next = Head;
    Head->next = NULL;

    return new_head;
}

递归方法隐藏了迭代法要考虑的一些细节。我们认为 reverse_recur() 能够接受一个
表头 Head 作为参数，然后返回反转后链表的新表头 new_head 。

方法三：

这种方法比前两种方法更直观，但是要浪费更多的资源。不提倡使用这种实现方法。

Node *reverse_array(Node *Head)
{
    Node **array;
    Node *p, *new_head;
    int num = 0;
    int i = 0;

    if (Head == NULL)
        return Head;
    
    for (p = Head; p != NULL; p = p->next)
        num++;

    // 动态分配一个 Node 指针的数组，用以存储所有 Node 节点
    array = (Node **)malloc(sizeof(Node *)*num);
    if (array == NULL) {
        printf("Out of memory!\n");
        exit(0);
    }

    for (p = Head; p != NULL; p = p->next) {
        array[i] = p;
        i++;
    }
    for (i=num-1; i > 0; i--)
        array[i]->next = array[i-1];

    array[0]->next = NULL;
    new_head = array[num-1];
    free(array);

    return new_head;
}

本文的中反转单链表的实现和测试代码可以在我的 github 中获得:
[https://github.com/hcyvan/webSiteCode/blob/master/c/
reverse_singly_linked_list.c](https://github.com/hcyvan/webSiteCode/blob/
master/c/reverse_singly_linked_list.c)