链表的五种反转方式

链表的反转是链表使用的一个重要操作，接下来本文将介绍 5 种反转方法。

1. 迭代法

• 核心思想：运用三个指针prev, cur, next遍历链表，依次将cur所在的节点反转，通过「保存后续节点→反转当前指针→移动指针」的循环逻辑，逐步完成整个链表的反转，最终让原链表尾节点成为新表头。

指针名称	初始状态	核心作用	迭代中变化规律
prev	NULL	指向「已完成反转的子链表」的尾节点	每次迭代后更新为当前cur节点
cur	原链表的head	指向「当前正在处理、待反转的节点」	每次迭代后更新为next节点
next	临时未赋值	暂存cur的下一个节点，避免反转后断链	每次迭代前从cur->next获取

struct ListNode* reverseList(struct ListNode* head) {
    if(head == NULL || head->next ==NULL){
        return head;
    }
    
    struct ListNode* cur = head;
    struct ListNode* prev = NULL;
    struct ListNode* next;
    
    while(cur){
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    
    return prev;

}

图片给出第一次循环的操作，之后依次往复直到cur指向NULL。

最后prev指向原链表的尾节点（即反转链表的头节点）。

2.头插法

• 核心思想：

  1. 新头 newHead 初始为空，相当于“空链表”；

  2. 遍历原链表时，先抓牢原链表的“下一个节点”（避免断链）；

  3. 把当前节点“掰弯”，让它指向新头（接入新链表）；

  4. 新头前移到当前节点（新链表变长），原头后移继续处理。

代码示例

struct ListNode* reverseList(struct ListNode* head) {
    if(head == NULL || head->next ==NULL){
        return head;
    }
    struct ListNode* newhead = (struct ListNode*)malloc(sizeof(struct ListNode));
    newhead->next = NULL;
    struct ListNode* prev = head;
    struct ListNode* cur = head->next;
    while(prev){
			prev->next = newhead->next;
			newhead->next = prev;
			prev = cur;
            if(cur != NULL){
			    cur = cur->next;
            }
	}
	struct ListNode* result = newhead->next;
	free(newhead);
	return result;
}

第一次头插

第二次头插

3.递归法

• 核心思想：把「反转整个链表」的大问题，拆解为「反转当前节点之后的子链表」的小问题，先递归解决子链表的反转，再通过回溯调整当前节点与子链表的指针关系，最终实现整个链表的反转。

代码示例：

struct ListNode* reverseList(struct ListNode* head) {
    // 1. 递归终止条件：空链表或最后一个节点（无需反转）
    if (head == NULL || head->next == NULL) {
        return head;  // 返回当前节点（将成为反转后的新头）
    }

    // 2. 递归处理：反转当前节点后面的子链表，得到子链表的新头
    struct ListNode* newHead = reverseList(head->next);

    // 3. 回溯操作：调整当前节点与子链表的指针关系
    head->next->next = head;  // 让子链表的尾节点（原head->next）指向当前节点
    head->next = NULL;        // 避免循环引用，当前节点成为新的尾节点

    // 4. 返回新头节点（始终是最底层递归返回的最后一个节点）
    return newHead;
}

递归反转链表简单来说：从链表末尾开始，先搞定最后两个的反转，再一步步往前反转每个节点与它后面已反转链表的关系。

4. 原地反转法

• 核心思想：
  1. 不额外造新节点，就用原链表的节点；
  2. 把每个节点的 “指向” 反过来（比如原本 1→2，改成 2→1）；
  3. 改之前先记住下一个节点，别弄丢，再逐个推进改完所有。

代码示例：

struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL) return NULL; 
    struct ListNode *prev = head;
    struct ListNode *current = head->next;
    while (current != NULL) {
        prev->next = current->next;
        current->next = head;
        head = current;
        current = prev->next;
    }
    return head;
}

每一次反转都会将两个节点反转。

• 示例：1->2->3->4
  1. 第一次反转：2->1->3->4
  2. 第二次反转：3->2->1->4
  3. 第三次反转：4->3->2->1

5. 栈辅助法

• 核心思想：
  1. 遍历原链表，把每个节点依次 “压” 进栈里（先压头节点，最后压尾节点）；
  2. 把栈里的节点逐个 “弹” 出来，按弹出顺序重新连接（尾节点先弹，变成新头节点；头节点最后弹，变成新尾节点）；
  3. 最后给新尾节点的next设为NULL，避免循环。

代码示例：

struct ListNode* reverseList(struct ListNode* head) {
    // 边界：空链表直接返回
    if (head == NULL) return NULL;

    // 1. 用数组模拟栈（假设链表长度不超过1e4，实际可动态扩容，这里简化）
    struct ListNode* stack[10000];
    int top = -1;  // 栈顶指针（-1表示空栈）

    // 2. 遍历链表，节点压栈
    struct ListNode* curr = head;
    while (curr != NULL) {
        stack[++top] = curr;  // 栈顶上移，压入当前节点
        curr = curr->next;
    }

    // 3. 弹栈，重新连接节点
    struct ListNode* newHead = stack[top--];  // 栈顶节点（原尾）是新头
    curr = newHead;  // 用于遍历新链表
    while (top != -1) {
        curr->next = stack[top--];  // 弹栈，连接下一个节点
        curr = curr->next;          // 新链表指针后移
    }

    // 4. 新尾节点的next设为NULL（避免循环）
    curr->next = NULL;

    return newHead;
}

栈辅助法就是利用了**“先进后出”**的特性，用空间换时间，先 push 整个链表，再 pop 整个链表，将链表反转。