反转链表：将链表整体“反过来”，将头变成尾、尾变成头。

反转的链表

反转后的链表

常见的四种方法:

迭代反转法
递归反转法
就地逆置法
头插法

递归反转法更适用于反转不带头节点的链表；其它 3 种方法既能反转不带头节点的链表，也能反转带头节点的链表。

迭代反转链表

方法：从当前链表的首元节点开始，一直遍历至链表的最后一个节点，这期间会逐个改变所遍历到的节点的指针域，另其指向前一个节点。

具体实现：借助 3 个指针即可。首先我们定义 3 个指针并分别命名为 beg、mid、end。它们的初始指向如下图所示。

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

3 个指针每次各向后移动一个节点（end 不为 NULL）
改变 head 头指针的指向，另其和 mid 同向（end 为 NULL）

//迭代反转法，head 为无头节点链表的头指针
link * iteration_reverse(link* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    else {
        link * beg = NULL;
        link * mid = head;
        link * end = head->next;
        //一直遍历
        while (1)
        {
            //修改 mid 所指节点的指向
            mid->next = beg;
            //此时判断 end 是否为 NULL，如果成立则退出循环
            if (end == NULL) {
                break;
            }
            //整体向后移动 3 个指针
            beg = mid;
            mid = end;
            end = end->next;
        }
        //最后修改 head 头指针的指向
        head = mid;
        return head;
    }
}

递归反转链表

方法：从链表的尾节点开始，依次向前遍历，遍历过程依次改变各节点的指向，即另其指向前一个节点。

link* recursive_reverse(link* head) {
    //递归的出口
    if (head == NULL || head->next == NULL)     // 空链或只有一个结点，直接返回头指针
    {
        return head;
    }

    else
    {
        //一直递归，找到链表中最后一个节点

        link *new_head = recursive_reverse(head->next);

        //当逐层退出时，new_head 的指向都不变，一直指向原链表中最后一个节点；
        //递归每退出一层，函数中 head 指针的指向都会发生改变，都指向上一个节点。

        //每退出一层，都需要改变 head->next 节点指针域的指向，同时令 head 所指节点的指针域为 NULL。
        head->next->next = head;
        head->next = NULL;

        //每一层递归结束，都要将新的头指针返回给上一层。由此，即可保证整个递归过程中，能够一直找得到新链表的表头。
        return new_head;
    }
}

由于 head 不为 NULL，因此函数每执行到第 11 行时，递归都会深入一层，并依次将指向节点 2、3、4 的指针作为实参（head_next 的指向）参与递归。而根据递归出口的判断条件，当函数参数 head 指向的是节点 4 时满足 head->next == NULL，递归过程不再深入，并返回指向节点 4 的指针，这就是反转链表的新头指针。

因此，当递归首次退出一层时，new_head 指向的是节点 4 ，而 head 由于退出一层，指向的是节点 3，如下图所示。

在此基础上，开始执行 17、18 行代码，整个操作过程如下图所示，最后将 new_head 的指向继续作为函数的返回值，传给上一层的 new_head。

再退一层，此时 new_head 仍指向节点 4，而 head 退出一层后，指向的是节点 2。在此基础上执行 17、18 行代码，并最终将 new_head 的指向作为函数返回值，继续传给上一层的 new_head。整个操作过程如下图所示：

再退一层，此时 new_head 仍指向节点 4，而 head 退出一层后，指向的是节点 1。在此基础上执行 17、18 行代码，并返回 new_head。整个操作过程如下图所示：

head 由节点 1 进入递归，此时 head 的指向又返回到节点 1，整个递归过程结束。显然，以上过程已经实现了链表的反转，新反转链表的头指针为 new_head。

头插法反转链表

方法：在原有链表的基础上，依次将位于链表头部的节点摘下，然后采用从头部插入的方式生成一个新链表，则此链表即为原链表的反转版。

步骤：

创建一个新的空链表

从原链表中摘除头部节点 i（i < N），并以头部插入的方式将该节点添加到新链表中

link * head_reverse(link * head) {
    link * new_head = NULL;
    link * temp = NULL;
    if (head == NULL || head->next == NULL) {
        return head;
    }
    while (head != NULL)
    {
        temp = head;
        //将 temp 从 head 中摘除
        head = head->next;

        //将 temp 插入到 new_head 的头部
        temp->next = new_head;
        new_head = temp;
    }
    return new_head;
}

就地逆置法反转链表

方法：就地逆置法和头插法的实现思想类似，唯一的区别在于，头插法是通过建立一个新链表实现的，而就地逆置法则是直接对原链表做修改，从而实现将原链表反转。

在原链表的基础上做修改，需要额外借助 2 个指针（假设分别为 beg 和 end）

步骤：

初始状态下，令 beg 指向第一个节点，end 指向 beg->next，如下图所示：

将 end 所指节点 2 从链表上摘除，然后再添加至当前链表的头部。如下图所示：

将 end 指向 beg->next，然后将 end 所指节点 3 从链表摘除，再添加到当前链表的头部，如下图所示：

将 end 指向 beg->next，再将 end 所示节点 4 从链表摘除，并添加到当前链表的头部，如下图所示：

link * local_reverse(link * head) {
    link * beg = NULL;
    link * end = NULL;
    if (head == NULL || head->next == NULL) {
        return head;
    }
    beg = head;
    end = head->next;
    while (end != NULL) {
        //将 end 从链表中摘除
        beg->next = end->next;
        //将 end 移动至链表头
        end->next = head;
        head = end;
        //调整 end 的指向，另其指向 beg 后的一个节点，为反转下一个节点做准备
        end = beg->next;
    }
    return head;
}

本博客采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议(CC BY-NC-SA 4.0) 发布.

Page View

单链表的反转

迭代反转链表

递归反转链表

头插法反转链表

就地逆置法反转链表