C++程序 单链表中交替K节点翻转

问题描述

给定一个单链表和一个数字K，在单链表中交替翻转每K个节点。换句话说，将每K个节点翻转，但前K个节点不变，接下来的K个节点翻转，然后再接下来的K个节点不变，以此类推。

例如，对于链表1->2->3->4->5->6->7和K=3，应该返回链表3->2->1->6->5->4->7。

解决方案

我们可以使用一个递归方案来解决此问题。我们将链表分为前K个节点和后面的节点。将前K个节点翻转，并将其余部分递归地解决，然后将两个部分连接起来。

让我们看看如何实现递归函数。

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* curr = head;
    int count = 0;
    while (curr != nullptr && count != k) {
        curr = curr->next;
        count++;
    }
    if (count == k) {
        curr = reverseKGroup(curr, k);
        while (count-- > 0) {
            ListNode* tmp = head->next;
            head->next = curr;
            curr = head;
            head = tmp;
        }
        head = curr;
    }
    return head;
}

在上面的递归函数中，我们首先统计链表中的前k个节点，然后我们递归地解决剩余的节点，并返回反转后的第一个节点。
接下来，我们将前K个节点反转。这可以通过翻转节点的指针来完成。一旦我们完成前K个节点的反转，我们将其连接到余下的部分，并返回反转后的第一个节点，如下所示：

if (count == k) {
    curr = reverseKGroup(curr, k);
    while (count-- > 0) {
        ListNode* tmp = head->next;
        head->next = curr;
        curr = head;
        head = tmp;
    }
    head = curr;
}

完整代码

以下是完整的C++实现，包括单链表的基本定义。使用输入和输出输出链表，测试上述方案。

#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* curr = head;
    int count = 0;
    while (curr != nullptr && count != k) {
        curr = curr->next;
        count++;
    }
    if (count == k) {
        curr = reverseKGroup(curr, k);
        while (count-- > 0) {
            ListNode* tmp = head->next;
            head->next = curr;
            curr = head;
            head = tmp;
        }
        head = curr;
    }
    return head;
}

void printList(ListNode* head) {
    while (head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

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);
    head->next->next->next->next->next = new ListNode(6);
    head->next->next->next->next->next->next = new ListNode(7);

    int k = 3;

    cout << "Original list: ";
    printList(head);

    head = reverseKGroup(head, k);

    cout << "Reversed " << k << " nodes in groups: ";
    printList(head);

    return 0;
}

输出将是：

Original list: 1 2 3 4 5 6 7 
Reversed 3 nodes in groups: 3 2 1 6 5 4 7 

结论

在这篇文章中，我们通过递归实现了C++单链表中交替K节点翻转程序。代码实现简单，但需要理解递归的实现过程。注意在代码中，我们需要考虑处理链表剩余部分时的边界情况，比如链表不足K个节点的情况。希望本文能对有相应需求的读者有一定帮助。