C语言算法-解答K个一组翻转链表问题的C语言实现

题目

给定一个链表，每 K 个节点一组进行翻转，返回翻转后的链表。如果链表的节点数不是 K 的倍数，则最后剩余的节点保持原样。

引言

K个一组翻转链表问题需要考虑链表的指针操作和节点翻转的逻辑。我们可以使用迭代的方法来解决这个问题，通过分组翻转链表的每个子区间。解决这个问题需要对链表进行指针操作和节点翻转。

算法思路

我们将使用迭代的方法来解决K个一组翻转链表问题。

算法的步骤如下：

1. 创建一个虚拟头结点 dummy，并将其指向原链表的头结点。
2. 创建两个指针 prev 和 end，初始化为 dummy。

3. 循环遍历链表，直到 end到达链表末尾：

   • 将 end 指针向后移动 K 个节点，如果剩余的节点不足 K 个，则停止移动。
   • 如果 end 到达链表末尾，则不需要翻转剩余的节点，直接退出循环。
   • 否则，记录 start 指针，它是当前子区间的起始节点。
   • 将 end 的下一个节点保存为 next。
   • 断开子区间的尾部连接，将 end 的下一个节点设置为 NULL。
   • 翻转子区间，将 start 到 end 的节点进行翻转，并返回翻转后的头结点。
   • 将 prev 的下一个节点指向翻转后的头结点，将翻转后的尾部节点连接到 next。
   • 更新 prev 和 end，将它们都指向翻转后的尾部节点。
4. 返回虚拟头结点的下一个节点，即翻转后的新链表的头结点。

代码实现

下面是使用C语言实现的代码：

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

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

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* dummy = (ListNode*)malloc(sizeof(ListNode));
    dummy->next = head;

    ListNode* prev = dummy;
    ListNode* end = dummy;

    while (end->next != NULL) {
        for (int i = 0; i < k && end != NULL; i++) {
            end = end->next;
        }

        if (end == NULL) {
            break;
        }

        ListNode* start = prev->next;
        ListNode* next = end->next;

        end->next = NULL;
        prev->next = reverseList(start);
        start->next = next;

        prev = start;
        end = start;
    }

    ListNode* newHead = dummy->next;
    free(dummy);

    return newHead;
}

ListNode* reverseList(ListNode* head) {
    ListNode* prev = NULL;
    ListNode* current = head;

    while (current != NULL) {
        ListNode* next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }

    return prev;
}

void printList(ListNode* head) {
    ListNode* current = head;

    while (current != NULL) {
        printf("%d ", current->val);
        current = current->next;
    }

    printf("\n");
}

int main() {
    // 创建示例链表: 1 -> 2 -> 3 -> 4 -> 5
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    head->val = 1;

    ListNode* node1 = (ListNode*)malloc(sizeof(ListNode));
    node1->val = 2;
    head->next = node1;

    ListNode* node2 = (ListNode*)malloc(sizeof(ListNode));
    node2->val = 3;
    node1->next = node2;

    ListNode* node3 = (ListNode*)malloc(sizeof(ListNode));
    node3->val = 4;
    node2->next = node3;

    ListNode* node4 = (ListNode*)malloc(sizeof(ListNode));
    node4->val = 5;
    node3->next = node4;
    node4->next = NULL;

    printf("Original List: ");
    printList(head);

    int k = 2;
    ListNode* result = reverseKGroup(head, k);

    printf("Reversed List: ");
    printList(result);

    // 释放内存
    while (result != NULL) {
        ListNode* temp = result;
        result = result->next;
        free(temp);
    }

    return 0;
}

算法分析

该算法需要对链表进行两次遍历：第一次遍历是在找到每个子区间的起始节点和尾部节点，第二次遍历是在翻转子区间。所以时间复杂度为 O(n)，其中 n 是链表的长度。

空间复杂度为 O(1)，算法只使用了常数级别的额外空间。

示例和测试

示例输入:

Original List: 1 -> 2 -> 3 -> 4 -> 5
k = 2

示例输出:

Reversed List: 2 -> 1 -> 4 -> 3 -> 5

总结

本文使用C语言实现了解答K个一组翻转链表问题的代码。通过使用迭代的方法，我们能够将链表每 K 个节点作为一组进行翻转，并返回翻转后的链表。该算法的时间复杂度为 O(n)，空间复杂度为 O(1)。