C++程序分组反转链表 – 第一部分

在编写C++程序时，经常需要操作链表来存储和处理数据。链表是一个重要的数据结构，它可以用来实现栈、队列、队列等常见的数据结构。在链表的基础上，可以实现更复杂的数据结构，如树、图等。

本篇文章将介绍如何使用C++实现链表分组反转的功能。具体来说，我们将实现一个函数，输入链表和一个整数k，将链表分成长度为k的若干组，然后将每一组的元素反转。最后，将所有的组合在一起，重新构成一个新的链表并返回。

数据结构定义和初始化

我们首先需要定义链表的基本数据结构，并初始化测试数据。

#include<iostream>
using namespace std;

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

int main(void) {
    ListNode* head = new ListNode(1);
    ListNode* curr = head;
    for (int i = 2; i <= 5; i++) {
        ListNode* node = new ListNode(i);
        curr->next = node;
        curr = node;
    }
    return 0;
}

上述代码用于创建一个5个元素的链表。

逻辑实现和代码

首先，我们需要确定链表的长度，这可以通过遍历链表来实现。我们还需要明确每个组的起始节点和结束节点，这可以通过计算来实现。接下来，我们需要将每个组内的元素反转，这可以通过遍历组内的元素来实现。

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* dummy = new ListNode(-1);
    dummy->next = head;
    ListNode* prev = dummy;

    int len = 0;
    for (ListNode* p = head; p != NULL; p = p->next) len++;

    while (len >= k) {
        ListNode* curr = prev->next;
        ListNode* tail = curr;
        for (int i = 1; i < k; i++) {
            tail = tail->next;
        }
        for (int i = 1; i < k; i++) {
            ListNode* temp = curr->next;
            curr->next = temp->next;
            temp->next = prev->next;
            prev->next = temp;
        }
        prev = curr;
        len -= k;
    }

    return dummy->next;
}

完整代码

#include<iostream>
using namespace std;

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

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* dummy = new ListNode(-1);
    dummy->next = head;
    ListNode* prev = dummy;

    int len = 0;
    for (ListNode* p = head; p != NULL; p = p->next) len++;

    while (len >= k) {
        ListNode* curr = prev->next;
        ListNode* tail = curr;
        for (int i = 1; i < k; i++) {
            tail = tail->next;
        }
        for (int i = 1; i < k; i++) {
            ListNode* temp = curr->next;
            curr->next = temp->next;
            temp->next = prev->next;
            prev->next = temp;
        }
        prev = curr;
        len -= k;
    }

    return dummy->next;
}

int main(void) {
    ListNode* head = new ListNode(1);
    ListNode* curr = head;
    for (int i = 2; i <= 5; i++) {
        ListNode* node = new ListNode(i);
        curr->next = node;
        curr = node;
    }

    ListNode* p = reverseKGroup(head, 2);
    while (p != NULL) {
        cout << p->val << " ";
        p = p->next;
    }

    return 0;
}