带头节点单链表就地逆序算法详解

问题定义

给定带头节点的单链表 head → 1 → 2 → 3 → 4 → 5 → NULL，要求原地逆序为 head → 5 → 4 → 3 → 2 → 1 → NULL，头节点本身不存数据，仅作为哨兵。

三种经典实现

方法一：头插法（最简洁）

void reverse_head_insert(Node *head) {
    Node *cur = head->next;
    head->next = NULL;            // 将原链表摘空，头节点变为新链表头
    while (cur) {
        Node *nxt = cur->next;
        cur->next = head->next;   // 头插
        head->next = cur;
        cur = nxt;
    }
}

时间 O(n)，空间 O(1)，代码极短，推荐面试首选。

方法二：三指针迭代（原代码风格）

void reverse_three_ptr(Node *head) {
    if (!head->next || !head->next->next) return; // 0 或 1 个数据节点
    Node *prev = head->next;      // 原首节点
    Node *curr = prev->next;      // 第二节点
    prev->next = NULL;            // 断开首节点 next
    while (curr->next) {          // 当 curr 非尾节点
        Node *nxt = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nxt;
    }
    curr->next = prev;            // 处理尾节点
    head->next = curr;            // 头节点指向新首节点
}

原代码逻辑正确，但循环条件 curr->next 需额外处理尾节点，稍显繁琐。

方法三：递归（优雅但有栈溢出风险）

Node* reverse_rec(Node *curr) { // 返回新头节点
    if (!curr || !curr->next) return curr;
    Node *new_head = reverse_rec(curr->next);
    curr->next->next = curr;
    curr->next = NULL;
    return new_head;
}
void reverse_rec_wrapper(Node *head) {
    head->next = reverse_rec(head->next);
}

完整可运行测试程序

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int data; struct Node *next; } Node;

Node* create_list(int n) {
    Node *head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    Node *tail = head;
    for (int i = 1; i <= n; ++i) {
        Node *p = (Node*)malloc(sizeof(Node));
        p->data = i; p->next = NULL;
        tail->next = p; tail = p;
    }
    return head;
}

void print_list(Node *head) {
    for (Node *p = head->next; p; p = p->next) printf("%d ", p->data);
    puts("");
}

void reverse_head_insert(Node *head) {
    Node *cur = head->next;
    head->next = NULL;
    while (cur) {
        Node *nxt = cur->next;
        cur->next = head->next;
        head->next = cur;
        cur = nxt;
    }
}

int main() {
    Node *head = create_list(5);
    print_list(head);          // 1 2 3 4 5
    reverse_head_insert(head);
    print_list(head);          // 5 4 3 2 1
    return 0;
}

常见坑点

• 忘记处理空表或单节点表。
• 头插法未将 head->next 置 NULL 导致成环。
• 三指针法循环条件写错（如 curr 而非 curr->next）导致尾节点丢失。
• 释放内存时未遍历完整链表造成泄漏。

扩展：LeetCode 206 / 92 变体

• 206 反转链表：无头节点版，返回新头指针。
• 92 反转部分链表：定位 m,n 区间，同理头插或三指针局部反转。
• 25 K 个一组反转：分组应用头插法。

总结

带头节点单链表逆序，头插法代码最少、最不易错，是工程与面试的首选实现。理解“摘空原链、头插构建新链”的思想，可举一反三解决各类链表重排问题。