C语言实现单链表的例子

<think>嗯，我现在需要了解一下如何用C语言实现单链表的逆转。首先，我应该回忆一下单链表的基本结构。单链表每个节点包含数据和指向下一个节点的指针，对吧？比如定义一个结构体，里面有int data和struct Node* next这样的成员。那逆转链表的话，就是把每个节点的next指针指向前一个节点，而不是后一个。 不过具体怎么操作呢？可能涉及到遍历链表，同时改变指针的指向。之前好像听说过有迭代和递归两种方法。先想想迭代的方法。假设有一个当前节点current，它的前一个节点prev，还有下一个节点next。每次操作应该是把current的next指向prev，然后三个指针都向前移动。比如初始时prev是NULL，current是头节点。然后循环直到current为NULL，这时候prev应该就是新的头节点了。 让我试试写个例子。比如链表1->2->3->4->NULL。逆转之后应该是4->3->2->1->NULL。按照迭代的方法，初始prev=NULL，current=1。第一次循环，next是current->next也就是2。然后把current->next指向prev也就是NULL，这时候1的next就变成NULL了。然后prev变成current也就是1，current变成next也就是2。接下来，current是2，next是3，current->next指向prev也就是1，这样2的next指向1，然后prev变成2，current变成3。以此类推，直到current变成NULL，这时候prev就是新的头节点4。 那递归的方法呢？递归可能需要从链表的末尾开始反转。比如先递归到最后一个节点，作为新的头节点。然后每次返回的时候，将当前节点的下一个节点的next指向自己，并且自己的next置为NULL。比如对于1->2->3->4，递归到4的时候返回，此时新头是4。然后处理3，让4的next指向3，而3的next原本是4，现在变成NULL。这样一步步往回处理，最后整个链表就反转了。不过递归可能会有栈溢出的问题，如果链表很长的话。 那具体用C语言怎么实现呢？首先定义节点结构体： struct Node { int data; struct Node* next; }; 然后迭代方法实现反转函数： struct Node* reverse(struct Node* head) { struct Node* prev = NULL; struct Node* current = head; struct Node* next = NULL; while (current != NULL) { next = current->next; // 保存下一个节点 current->next = prev; // 反转当前节点的指针 prev = current; // prev移动到当前 current = next; // current移动到下一个 } head = prev; // 最后prev是新的头节点 return head; } 这个逻辑应该对吧？测试一下，比如原链表是1->2->3->4，第一次循环后current是1，next是2，current->next变成NULL，prev变成1，current变成2。下一次循环current是2，next是3，current->next指向1，prev变成2，current变成3。依此类推，最后prev是4，作为新的头。 递归方法的话： struct Node* reverseRecursive(struct Node* head) { if (head == NULL || head->next == NULL) { return head; // 空链表或最后一个节点时返回 } struct Node* newHead = reverseRecursive(head->next); head->next->next = head; // 下一个节点指向自己 head->next = NULL; // 自己的next设为NULL return newHead; } 比如处理节点3的时候，此时head是3，head->next是4。递归调用返回后，newHead是4。然后head->next->next即4的next指向3，而3的next设为NULL，这样4->3。然后返回到处理2的时候，同样操作，让3的next指向2，依此类推，最终形成反转后的链表。 不过要注意递归的终止条件，当head为空或者head->next为空时返回head，这对应着空链表或者最后一个节点的情况。 那用户可能还需要了解如何测试这个反转函数。比如创建链表，打印链表，然后反转后再次打印。比如创建链表的函数可能如下： struct Node* createNode(int data) { struct Node* node = (struct Node*)malloc(sizeof(struct Node)); node->data = data; node->next = NULL; return node; } 然后可以手动链接节点，或者通过循环插入来创建链表。之后写一个打印函数，遍历链表输出每个节点的数据。 测试的时候，可能会有内存管理的问题，需要确保没有内存泄漏。不过这可能属于更高级的话题，用户可能暂时不需要。 总结一下，实现单链表逆转主要有两种方法：迭代法和递归法。迭代法通过三个指针依次改变节点指向，而递归法则从后往前逐个节点反转。两种方法的时间复杂度都是O(n)，空间复杂度迭代是O(1)，递归是O(n)因为递归栈的深度。 需要注意，递归方法在链表很长时可能导致栈溢出，而迭代方法更安全。此外，处理头节点和空链表的情况也是关键，避免出现空指针访问。</think>下面分步骤介绍C语言实现单链表逆转的两种核心方法： --- ### 一、单链表结构定义 ```c struct Node { int data; // 存储数据 struct Node* next; // 指向下一个节点的指针 }; ``` --- ### 二、迭代法实现逆转 #### 步骤拆解 1. **初始化指针** - `prev`：初始化为`NULL`（最终指向新头节点） - `current`：初始化为头节点`head`（当前处理节点） - `next`：临时保存下一个节点 2. **遍历链表并反转指针** ```c struct Node* reverse(struct Node* head) { struct Node *prev = NULL, *current = head, *next = NULL; while (current != NULL) { next = current->next; // 保存下一个节点 current->next = prev; // 反转当前节点的指针 prev = current; // prev前移 current = next; // current前移 } return prev; // prev最终指向新头节点 } ``` 3. **时间复杂度** $$O(n)$$，仅需遍历一次链表。 --- ### 三、递归法实现逆转 #### 步骤拆解 1. **递归终止条件** - 链表为空或只剩一个节点时，直接返回当前头节点。 2. **递归到链表末尾** ```c struct Node* reverseRecursive(struct Node* head) { if (head == NULL || head->next == NULL) { return head; // 终止条件 } struct Node* newHead = reverseRecursive(head->next); // 后续操作... } ``` 3. **反转当前节点与下一节点的指向** ```c head->next->next = head; // 下一节点指向当前节点 head->next = NULL; // 当前节点指向NULL return newHead; // 始终返回末尾节点（新头节点） ``` 4. **时间复杂度** $$O(n)$$，递归深度为链表长度。 --- ### 四、完整代码示例 ```c #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; }; // 迭代法反转链表 struct Node* reverse(struct Node* head) { struct Node *prev = NULL, *current = head, *next = NULL; while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } return prev; } // 递归法反转链表 struct Node* reverseRecursive(struct Node* head) { if (head == NULL || head->next == NULL) { return head; } struct Node* newHead = reverseRecursive(head->next); head->next->next = head; head->next = NULL; return newHead; } // 创建新节点 struct Node* createNode(int data) { struct Node* node = (struct Node*)malloc(sizeof(struct Node)); node->data = data; node->next = NULL; return node; } // 打印链表 void printList(struct Node* head) { struct Node* current = head; while (current != NULL) { printf("%d -> ", current->data); current = current->next; } printf("NULL\n"); } int main() { // 创建示例链表 1 -> 2 -> 3 -> 4 -> NULL struct Node* head = createNode(1); head->next = createNode(2); head->next->next = createNode(3); head->next->next->next = createNode(4); printf("原链表: "); printList(head); // 使用迭代法反转 head = reverse(head); printf("迭代反转后: "); printList(head); // 再次反转恢复原链表（使用递归法） head = reverseRecursive(head); printf("递归反转后: "); printList(head); return 0; } ``` --- ### 五、关键注意事项 1. **空链表处理**：两种方法均兼容`head == NULL`的情况。 2. **内存安全**：实际项目中需确保无内存泄漏（示例未释放内存）。 3. **递归限制**：递归法在极长链表（如数万节点）时可能导致栈溢出。 --- 通过选择迭代或递归方法，即可高效实现单链表的逆转操作。

在C语言中，单链表的逆置可以采用迭代或递归的方式实现。这里我们先来看一下迭代的方法： ```c #include <stdio.h> #include <stdlib.h> // 定义链表结构体 typedef struct Node { int data; struct Node* next; } Node; // 函数声明 Node* reverseList(Node* head); // 主函数演示 void printList(Node* head) { while (head != NULL) { printf("%d ", head->data); head = head->next; } printf("\n"); } int main() { // 创建一个示例链表 Node* list = (Node*)malloc(sizeof(Node)); list->data = 1; list->next = (Node*)malloc(sizeof(Node)); list->next->data = 2; list->next->next = (Node*)malloc(sizeof(Node)); list->next->next->data = 3; list->next->next->next = NULL; printf("Original List: "); printList(list); // 逆置链表 list = reverseList(list); printf("Reversed List: "); printList(list); return 0; } // 实现链表逆置 Node* reverseList(Node* head) { Node *prev = NULL, *current = head, *next = NULL; while (current != NULL) { next = current->next; // 保存当前节点的下一个节点 current->next = prev; // 将当前节点指向前一个节点 prev = current; // 更新前一个节点为当前节点 current = next; // 移动到下一个节点 } return prev; // 返回新的头节点，即原链表的尾部 } ``` 在这个例子中，`reverseList`函数通过三个指针（prev、current和next）来遍历并改变链表的连接。最后返回prev，它现在成为了新的头节点。