056 单链表就地逆置 C语言

单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据以及指向下一个节点的指针。在C语言中，实现单链表的操作是非常基础且重要的编程技能。本话题将探讨如何就地逆置一个单链表，即不使用额外的数据结构或数组，仅通过链表自身的节点进行操作。 我们要理解链表的逆置意味着原来的顺序是 head -> node1 -> node2 -> ... -> nodeN，逆置后变成 head -> nodeN -> nodeN-1 -> ... -> node1。为了实现这个操作，我们可以使用迭代或递归的方法。这里我们主要讨论迭代方法，因为它是更有效率且易于理解的方式。 **迭代逆置单链表的步骤如下：** 1. 初始化三个指针：`prev`（前一个节点），`current`（当前节点）和`next`（下一个节点）。初始时，`prev` 设为 `NULL`，`current` 设为链表的头节点。 2. 在`current`不为空的情况下，执行以下操作： - 将`current`的`next`指针保存到`next`变量中，这将用于后续的链接操作。 - 将`current`的`next`指针指向`prev`，实现节点的逆向链接。 - 更新`prev`和`current`指针，将`prev`设为`current`，`current`设为`next`。 3. 当`current`为空时，表示已经遍历完整个链表。此时，将原链表的头节点（现在是最后一个节点）的`next`指针设为`NULL`，并更新头节点为`prev`，完成链表逆置。 下面是一个C语言的实现示例： ```c #include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node* next; } Node; // 创建新节点 Node* createNode(int data) { Node* newNode = (Node*)malloc(sizeof(Node)); if (newNode == NULL) { printf("Memory allocation failed.\n"); return NULL; } newNode->data = data; newNode->next = NULL; return newNode; } // 插入节点到链表尾部 Node* insertAtEnd(Node* head, int data) { Node* newNode = createNode(data); if (head == NULL) { return newNode; } Node* current = head; while (current->next != NULL) { current = current->next; } current->next = newNode; return head; } // 逆置链表 Node* reverseList(Node* head) { Node* prev = NULL; Node* current = head; Node* next; while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } return prev; } // 打印链表 void printList(Node* head) { while (head != NULL) { printf("%d -> ", head->data); head = head->next; } printf("NULL\n"); } int main() { Node* head = NULL; head = insertAtEnd(head, 1); head = insertAtEnd(head, 2); head = insertAtEnd(head, 3); head = insertAtEnd(head, 4); printf("Original list: "); printList(head); head = reverseList(head); printf("Reversed list: "); printList(head); return 0; } ``` 这段代码首先定义了单链表节点结构体`Node`，然后实现了创建新节点、在链表尾部插入节点、逆置链表以及打印链表的功能。在`main`函数中，我们创建了一个包含数字1到4的链表，打印原始链表，然后逆置链表并再次打印。 逆置链表是一个典型的链表操作，它对于理解和掌握链表数据结构至关重要。这个过程不仅可以帮助我们更好地理解链表的内部工作原理，而且在解决许多实际问题时，如LRU缓存、数据排序等，逆置链表都是常用技巧之一。