链表反转的原理和方法

链表是一种常见的数据结构，它由一系列的节点组成，每个节点包含一个数据域和一个指针域。链表的特点是可以灵活地增加或删除节点，而不需要连续的内存空间。链表有单向链表、双向链表、循环链表等不同类型。

链表反转是指将一个链表中的节点顺序颠倒过来，使得原来的头节点变成尾节点，原来的尾节点变成头节点，以及原来的每个节点都指向它的前一个节点。例如，如图 1 所示：

经过反转后，得到的新链表如图 2 所示：

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

那么如何实现这样一个操作呢？常用的实现方案有以下几种：

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

下面我们分别介绍这些方法，并给出相应的示例代码和注释。

1. 迭代反转法

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

具体地说，我们需要借助三个指针来完成这个操作：

• prev：指向当前遍历到的节点之前（左边）已经被反转过了部分子列表中最后（右边）一个元素。
• cur：指向当前遍历到并且正在被处理（即要被翻转）部分子列表中第一个（左边）元素。
• next：用于保存当前遍历到并且正在被处理部分子列表中第二个（右边）元素。

初始时，prev 指向空（因为还没有任何元素被翻转），cur 指向首元结点（因为首元结点是第一个要被翻转），next 指向第二个结点（因为要保存下一个要被翻转）。如图 3 所示：

然后我们开始迭代地执行以下步骤¹：

1. 将 cur->next 指针改为指向 prev
2. 将 prev 指针移动到 cur
3. 将 cur 指针移动到 next
4. 将 next 指针到 cur->next

重复这些步骤，直到 cur 指向空（即链表的最后一个节点的后一个位置），此时 prev 指向链表的最后一个节点（即反转后的首元节点），如图 4 所示：

因此，我们只需要返回 prev 即可得到反转后的链表。

用 C 语言实现该算法的示例代码如下¹：

// 定义链表结点结构体
struct ListNode {
    int val; // 数据域
    struct ListNode *next; // 指针域
};

// 迭代反转法
struct ListNode* reverseList(struct ListNode* head) {
    // 定义三个指针 prev、cur、next
    struct ListNode *prev = NULL;
    struct ListNode *cur = head;
    struct ListNode *next = NULL;

    // 遍历链表，逐个改变指针域的指向
    while (cur != NULL) {
        next = cur->next; // 保存下一个要被处理的节点
        cur->next = prev; // 将当前节点指向前一个节点
        prev = cur; // 将前一个节点移动到当前节点
        cur = next; // 将当前节点移动到下一个要被处理的节点
    }

    return prev; // 返回反转后的链表头结点
}

2. 递归反转法

该算法和迭代反转法的思想恰好相反，它是从链表的尾节点开始，依次向前遍历，遍历过程中依次改变各节点的指针域，使其指向前一个节点。

具体地说，我们需要借助两个指针来完成这个操作：

• head：指向当前正在被处理（即要被翻转）部分子列表中第一个（左边）元素。
• new_head：用于保存已经被处理过了部分子列表中第一个（左边）元素。

初始时，head 指向首元结点（因为首元结点是第一个要被翻转），new_head 指向空（因为还没有任何元素被翻转）。如图 5 所示：

然后我们开始递归地执行以下步骤：

1. 如果 head 或者 head->next 是空，则返回 head
2. 否则，将 head->next 节点作为新的 head 继续递归调用本函数，并将结果赋值给 new_head
3. 将原来的 head->next->next 指针改为指向原来的 head
4. 将原来的 head->next 指针改为指向空

重复这些步骤，直到递归结束，此时返回值就是反转后的链表头结点。如图 6 所示：

用 C 语言实现该算法的示例代码如下

// 定义链表结点结构体
struct ListNode {
    int val; // 数据域
    struct ListNode *next; // 指针域
};

// 递归反转法
struct ListNode* reverseList(struct ListNode* head) {
    // 定义两个指针 head 和 new_head
    struct ListNode *new_head = NULL;

    // 如果 head 或者 head->next 是空，则返回 head
    if (head == NULL || head->next == NULL) {
        return head;
    }

    // 否则，将 head->next 节点作为新的 head 继续递归调用本函数，并将结果赋值给 new_head
    new_head = reverseList(head->next);

    // 将原来的 head->next->next 指针改为指向原来的 head
    head->next->next = head;

    // 将原来的 head->next 指针改为指向空
    head->next = NULL;

    return new_head; // 返回反转后的链表头结点
}

3. 头插法

该算法是利用一个新建的空链表（带头节点或不带头节点均可），遍历原链表，将每个遍历到的节点插入到新链表的首部，从而实现链表反转。

具体地说，我们需要借助三个指针来完成这个操作：

• head：指向原链表中当前正在被处理（即要被翻转）部分子列表中第一个（左边）元素。
• cur：指向原链表中当前正在被处理（即要被翻转）部分子列表中最后一个（右边）元素。
• new_head：指向新建空链表中第一个（左边）元素。

初始时，head 指向首元结点（因为首元结点是第一个要被翻转），cur 指向空（因为还没有任何元素被翻转），new_head 指向新建空链表中唯一的头节点。如图 7 所示：

然后我们开始迭代地执行以下步骤

1. 如果 head 是空，则返回 new_head
2. 否则，将 head 节点从原链表中断开，并保存其下一个节点到 cur
3. 将 head 节点插入到新链表的首部，即将其放在 new_head 的后面，并更新 new_head
4. 将 cur 节点作为新的 head

重复这些步骤，直到迭代结束，此时返回值就是反转后的链表头结点。如图 8 所示：

用 C 语言实现该算法的示例代码如下

// 头插法
struct ListNode* reverseList(struct ListNode* head) {
    // 定义一个新建的空链表 new_head
    struct ListNode *new_head = NULL;

    // 定义一个指针 cur 用来保存 head 的下一个节点
    struct ListNode *cur = NULL;

    // 迭代地执行以下步骤
    while (head != NULL) {
        // 将 head 节点从原链表中断开，并保存其下一个节点到 cur
        cur = head->next;

        // 将 head 节点插入到新链表的首部，即将其放在 new_head 的后面，并更新 new_head
        head->next = new_head;
        new_head = head;

        // 将 cur 节点作为新的 head
        head = cur;
    }

    return new_head; // 返回反转后的链表头结点
}

这样就完成了头插法反转链表