设计一算法,逆置带头结点的动态链表L。要求利用原表的结点空间,并要求用尽可能少的时间完成。 提示 可以考虑用头插法思想将单链表中每个结点“卸”下来再“挂”上去。请用C语言编写完整代码
时间: 2024-09-24 07:08:54 浏览: 8
为了逆置一个带头结点的动态链表L,我们可以使用迭代的方式,通过三个指针prev、current和next来依次遍历链表。在遍历过程中,我们将当前节点的下一个节点指向prev,然后移动这三个指针。以下是C语言的详细代码:
```c
// 定义链表结构体
typedef struct ListNode {
int data;
struct ListNode *next;
} ListNode;
// 逆置链表函数
void reverseList(ListNode **head) {
if (*head == NULL || (*head)->next == NULL) {
// 如果链表为空或只有一个节点,无需反转
return;
}
ListNode *prev = NULL; // 初始化前驱指针
ListNode *current = *head; // 当前节点
ListNode *next暂存; // 存储当前节点的下一个
// 遍历链表,每次修改当前节点的next
while (current != NULL) {
next = current->next; // 保存当前节点的下一个
current->next = prev; // 将当前节点的next指向前驱
prev = current; // 更新前驱指针
current = next; // 移动到下一个节点
}
// 最后把新的头节点设为原头节点的下一个
*head = prev;
}
// 示例:
ListNode *head = ... // 初始化链表
reverseList(&head);
```
这段代码首先检查链表是否为空或只有一个节点,然后开始迭代,每次循环更新节点的next指针并移动指针位置,直到遍历完整个链表。最后,原头节点会变成新链表的尾部。