设计一个算法,将链表中所有结点的链接方向“原地”逆转,即要求仅利用原表的存储空间,换句话说,要求算法的空间复杂度为O(1)
时间: 2024-03-11 11:49:52 浏览: 152
写一个算法将一单链表逆置。要求操作在原链表上进行。
可以采用迭代的方式来原地逆转链表,具体实现如下:
1. 定义三个指针,分别为prev、curr、next,分别指向前一个结点、当前结点和下一个结点。
2. 初始化prev为NULL,curr为链表的头结点。
3. 遍历链表,直到curr为NULL。在遍历过程中,执行以下步骤:
a. 将next指针指向curr结点的下一个结点。
b. 将curr结点的next指针指向prev结点。
c. 将prev指针指向当前结点curr。
d. 将curr指针指向next。
4. 返回prev作为新的头结点。
代码实现如下:
```
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode *prev = NULL, *curr = head, *next;
while (curr) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
```
阅读全文