利用单链表表示一个整数序列,通过一趟遍历,将单链表中所有结点的链接方向逆转,要求空间复杂度为1
时间: 2024-10-07 08:04:50 浏览: 50
要使用单链表表示一个整数序列并反转其节点链接方向,但空间复杂度要求为 O(1),这意味着我们不能创建额外的数据结构或分配大量内存,因为我们需要在原地操作整个链表。我们可以采用迭代的方式,通过三个指针(当前节点、前一个节点和下一个节点)来实现这个过程。
以下是一个简单的 C 语言代码示例:
```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;
ListNode* curr = head;
ListNode* nextTemp = NULL; // 临时保存当前节点的下一个节点
// 遍历链表,每次迭代更新prev, curr和nextTemp指针
while (curr != NULL) {
nextTemp = curr->next;
curr->next = prev; // 将当前节点指向前一个节点
prev = curr; // 更新前一个节点为当前节点
curr = nextTemp; // 移动到下一个节点
}
return prev; // 最后返回新的头节点(原尾部)
}
```
在这个代码中,我们逐个节点地改变它们的 `next` 指针,使得原始的 `next` 指向了前一个节点。遍历结束后,`prev` 指向的就是新链表的头部,即原来的尾部。
阅读全文