c/c++蓝桥杯经典编程题100道（16）链表反转

链表反转

c/c++蓝桥杯经典编程题100道-目录-CSDN博客

目录

链表反转

一、题型解释

二、例题问题描述

三、C语言实现

解法1：迭代反转（难度★）

解法2：递归反转（难度★★）

解法3：分组反转（难度★★★）

四、C++实现

解法1：迭代反转（难度★）

解法2：使用STL容器辅助（难度★★）

五、总结对比表

六、特殊方法与内置函数补充

1. C++智能指针

2. 链表调试技巧

一、题型解释

链表反转是将链表节点的连接方向完全逆序的操作。常见题型：

1. 基础反转：反转整个单链表（如 1→2→3→4→5 转为 5→4→3→2→1）。

2. 部分反转：反转链表的某个区间（如反转第2到第4个节点）。

3. 分组反转：每k个节点为一组进行反转（如k=2时，1→2→3→4→5 转为 2→1→4→3→5）。

4. 递归反转：用递归思想实现链表反转。

二、例题问题描述

例题1：输入链表 1→2→3→4→5，输出反转后的链表 5→4→3→2→1。
例题2：输入链表 1→2→3→4→5 和区间 [2,4]，输出 1→4→3→2→5。
例题3：输入链表 1→2→3→4→5 和k=2，输出 2→1→4→3→5。
例题4：输入链表 1→2，输出 2→1。

三、C语言实现

解法1：迭代反转（难度★）

通俗解释：

• 像翻书一样，逐个节点改变指针方向，将当前节点的next指向前一个节点。

c

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

struct ListNode {
    int val;
    struct ListNode *next;
};

// 迭代反转链表
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL, *curr = head;
    while (curr != NULL) {
        struct ListNode *nextTemp = curr->next; // 保存下一个节点
        curr->next = prev; // 当前节点指向前一个节点
        prev = curr;       // 前一个节点后移
        curr = nextTemp;   // 当前节点后移
    }
    return prev; // prev最终指向新链表的头节点
}

// 打印链表
void printList(struct ListNode* head) {
    while (head != NULL) {
        printf("%d→", head->val);
        head = head->next;
    }
    printf("NULL\n");
}

int main() {
    // 构建链表 1→2→3→4→5
    struct ListNode node5 = {5, NULL};
    struct ListNode node4 = {4, &node5};
    struct ListNode node3 = {3, &node4};
    struct ListNode node2 = {2, &node3};
    struct ListNode node1 = {1, &node2};
    
    struct ListNode* newHead = reverseList(&node1);
    printList(newHead); // 输出 5→4→3→2→1→NULL
    return 0;
}

代码逻辑：

1. 初始化指针：prev（前一个节点）初始为NULL，curr（当前节点）初始为头节点。

2. 循环操作：

   • 保存下一个节点 nextTemp = curr->next。

   • 将当前节点的 next 指向 prev。

   • prev 和 curr 向后移动。

3. 终止条件：当 curr 为NULL时，prev 成为新链表的头节点。

解法2：递归反转（难度★★）

通俗解释：

• 假设后面的链表已经反转，只需处理当前节点和已反转部分的连接。

c

struct ListNode* reverseListRecursive(struct ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head; // 基线条件：空链表或只剩一个节点
    }
    struct ListNode* newHead = reverseListRecursive(head->next); // 递归反转后续链表
    head->next->next = head; // 当前节点的下一个节点指向自己（反转方向）
    head->next = NULL;       // 断开原有连接
    return newHead; // 返回新头节点
}

int main() {
    // 测试递归反转
    struct ListNode* newHead = reverseListRecursive(&node1);
    printList(newHead); // 输出 5→4→3→2→1→NULL
    return 0;
}

代码逻辑：

1. 基线条件：链表为空或只剩一个节点时直接返回。

2. 递归调用：先反转 head->next 之后的链表，得到新头节点 newHead。

3. 反转当前节点：将当前节点的下一个节点的 next 指向自己，再断开自己的 next。

4. 递归栈展开：从最后一个节点开始逐层反转。

解法3：分组反转（难度★★★）

通俗解释：

• 每k个节点为一组，组内反转，若剩余节点不足k个则保持原顺序。

c

struct ListNode* reverseKGroup(struct ListNode* head, int k) {
    struct ListNode *curr = head;
    int count = 0;
    // 检查是否足够k个节点
    while (curr != NULL && count < k) {
        curr = curr->next;
        count++;
    }
    if (count == k) { // 足够k个节点时反转
        struct ListNode *prev = reverseKGroup(curr, k); // 递归处理后续分组
        // 反转当前k个节点
        while (count-- > 0) {
            struct ListNode *nextTemp = head->next;
            head->next = prev;
            prev = head;
            head = nextTemp;
        }
        head = prev;
    }
    return head; // 不足k个时直接返回原头节点
}

int main() {
    // 测试分组反转（k=2）
    struct ListNode* newHead = reverseKGroup(&node1, 2);
    printList(newHead); // 输出 2→1→4→3→5→NULL
    return 0;
}

代码逻辑：

1. 检查分组长度：遍历链表，判断剩余节点是否足够k个。

2. 递归处理后续分组：若足够，递归反转后续链表，返回已反转部分的头节点。

3. 反转当前分组：用迭代法反转当前k个节点，连接到已反转部分。

4. 终止条件：若不足k个，直接返回当前头节点。

四、C++实现

解法1：迭代反转（难度★）

通俗解释：

• 与C语言迭代法逻辑相同，使用指针操作。

cpp

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *prev = NULL, *curr = head;
        while (curr != NULL) {
            ListNode *nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
};

int main() {
    ListNode *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    
    Solution sol;
    ListNode *newHead = sol.reverseList(head);
    while (newHead != NULL) {
        cout << newHead->val << "→";
        newHead = newHead->next;
    }
    cout << "NULL" << endl; // 输出 5→4→3→2→1→NULL
    return 0;
}

代码逻辑：

• 与C语言版本完全一致，但使用C++的类和对象封装。

解法2：使用STL容器辅助（难度★★）

通俗解释：

• 将链表存入容器（如栈或数组），反向构建新链表。

cpp

ListNode* reverseListSTL(ListNode* head) {
    vector<int> values;
    ListNode *curr = head;
    while (curr != NULL) { // 存入数组
        values.push_back(curr->val);
        curr = curr->next;
    }
    ListNode *dummy = new ListNode(0);
    curr = dummy;
    for (int i = values.size() - 1; i >= 0; i--) { // 反向遍历数组
        curr->next = new ListNode(values[i]);
        curr = curr->next;
    }
    return dummy->next;
}

int main() {
    ListNode *head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    
    ListNode *newHead = reverseListSTL(head);
    // 输出 3→2→1→NULL
    return 0;
}

代码逻辑：

1. 存储节点值：遍历链表，将节点的值存入数组。

2. 反向构建链表：从数组末尾开始遍历，创建新节点并连接。

3. 优点：代码简单，但空间复杂度为O(n)。

五、总结对比表

六、特殊方法与内置函数补充

1. C++智能指针

• 作用：自动管理内存，避免内存泄漏（需包含 <memory> 头文件）。

• 示例：

  shared_ptr<ListNode> node = make_shared<ListNode>(1);

2. 链表调试技巧

• 打印链表：编写打印函数时，可在每个节点后添加箭头（→），末尾标记 NULL。

• 图形化工具：使用在线数据结构可视化工具（如VisuAlgo）辅助调试。

c/c++蓝桥杯经典编程题100道-目录-CSDN博客