C语言算法-解答反转链表算法问题的C语言实现

题目

给定一个链表，反转该链表，返回反转后的链表。

引言

反转链表是一个常见的链表操作，通常在链表数据结构的处理中有广泛的应用。这个问题的核心思想是将链表的节点顺序颠倒，使得原链表的尾部变成新链表的头部。

在下面的部分中，我们将讨论如何使用C语言来解决反转链表问题。

算法思路

解决反转链表问题的一种常见方法是使用迭代。以下是算法的详细思路：

1. 初始化三个指针：prev、curr 和 next，分别指向前一个节点、当前节点和下一个节点。
2. 将 curr 指向 head，即链表的头节点。

3. 循环迭代，直到curr到达链表的末尾（即curr为 NULL）：

   • 将 next 指向 curr 的下一个节点。
   • 将 curr 的下一个节点指向 prev，实现反转。
   • 将 prev 和 curr 向前移动一步，继续迭代。
4. 当循环结束时，prev 指向原链表的末尾节点，即新链表的头节点。
5. 返回 prev 作为反转后的链表头。

代码实现

下面是C语言中解决反转链表问题的迭代方式的代码实现：

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

// 定义链表节点结构
struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode* prev = NULL;
    struct ListNode* curr = head;
    struct ListNode* next;

    while (curr != NULL) {
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }

    return prev;
}

// 创建链表节点
struct ListNode* createNode(int val) {
    struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

int main() {
    // 创建一个示例链表: 1 -> 2 -> 3 -> 4 -> 5
    struct ListNode* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    printf("原链表: 1 -> 2 -> 3 -> 4 -> 5\n");

    // 反转链表
    struct ListNode* reversedHead = reverseList(head);

    printf("反转后的链表: ");
    while (reversedHead != NULL) {
        printf("%d", reversedHead->val);
        if (reversedHead->next != NULL) {
            printf(" -> ");
        }
        reversedHead = reversedHead->next;
    }
    printf("\n");

    return 0;
}

算法分析

这个反转链表的迭代算法的时间复杂度是O(n)，其中n是链表的长度，因为我们需要遍历整个链表。空间复杂度是O(1)，因为我们只使用了常数额外空间。

示例和测试

让我们使用一个示例来测试我们的反转链表的程序。假设我们有一个链表1 -> 2 -> 3 -> 4 -> 5。运行上述代码，我们将得到以下输出：

原链表: 1 -> 2 -> 3 -> 4 -> 5
反转后的链表: 5 -> 4 -> 3 -> 2 -> 1

这表明我们成功地反转了链表。

总结

反转链表是一个常见的链表操作问题，通常在链表数据结构的处理中有广泛的应用。通过使用迭代方法，我们可以高效地解决这个问题，颠倒链表的节点顺序。在本文中，我们使用C语言实现了一个反转链表的迭代算法。通过详细讨论算法思路、代码实现、算法分析以及示例和测试，我们希望读者能够理解并运用这一概念来解决类似的问题。反转链表问题在链表操作和数据结构领域具有广泛的应用，因此对对算法和数据结构有兴趣的程序员来说是一个有用的问题。