利用单链表表示一个整数序列,通过一趟遍历,将单链表中所有结点的链接方向逆转。
时间: 2024-10-07 17:04:43 浏览: 55
要利用单链表表示一个整数序列并逆转其节点链接的方向,你可以使用迭代或递归的方法。这里提供一种使用迭代的方式:
```c
// 定义链表节点结构
typedef struct ListNode {
int val; // 节点值
struct ListNode *next; // 指向下一个节点的指针
} ListNode;
// 函数用于反转链表
ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) { // 基线条件:空链表或只有一个节点
return head;
}
ListNode *prev = NULL, *curr = head, *temp = NULL; // 初始化前驱、当前和临时指针
while (curr != NULL) { // 遍历链表
temp = curr->next; // 保存当前节点的下一个节点
curr->next = prev; // 将当前节点的next指向前驱
prev = curr; // 更新前驱为当前节点
curr = temp; // 更新当前节点为下一个节点
}
return prev; // 返回新头节点(原尾部)
}
```
这段代码首先检查链表是否为空或只有一个节点,如果是,则直接返回。然后初始化三个指针:`prev`指向NULL(开始时没有前驱),`curr`指向链表头,`temp`暂时存储`curr`的下一个节点。在循环中,每次迭代都会改变`curr`的`next`指针,使其指向`prev`,然后前进到下个节点。当循环结束时,`prev`将成为新的头节点。
阅读全文