设计一个算法,将链表中所有结点的链接方向“原地”逆转,即要求仅利用原表的存储空间,换句话说,要求算法的空间复杂度为O(1)。
时间: 2024-03-11 07:50:51 浏览: 32
可以使用三个指针来完成该算法,分别指向当前遍历的结点、其前驱结点和其后继结点。具体步骤如下:
1. 初始化三个指针pre、cur、next,分别指向头结点的前驱结点、头结点和头结点的后继结点。
2. 遍历链表,依次将cur的next指向pre,然后将pre、cur、next指针依次向后移动一个结点,直到遍历到链表的末尾。
3. 将头结点的next指向pre,完成链表的反转。
以下是具体的代码实现:
```c++
void reverseList(ListNode* head) {
if(head == NULL || head->next == NULL) {
return;
}
ListNode* pre = NULL;
ListNode* cur = head;
ListNode* next = head->next;
while(next != NULL) {
cur->next = pre;
pre = cur;
cur = next;
next = next->next;
}
cur->next = pre;
head->next = cur;
}
```
需要注意的是,该算法的时间复杂度为O(n),其中n为链表的长度。空间复杂度为O(1),符合题目要求。
相关问题
设计一个算法,将链表中所有结点的链接方向逆转,仍利用原表的存储空间。的代码实现
可以使用三个指针 prev、curr 和 next,分别表示当前节点的前一个节点、当前节点和当前节点的后一个节点。初始时,prev 为 NULL,curr 为链表的头节点。然后依次遍历链表中的每个节点,将当前节点的 next 指针指向 prev,然后将 prev、curr、next 三个指针依次向后移动一个节点。遍历完成后,prev 就指向了原链表的尾节点,curr 则成为了新的头节点。
下面是算法的具体实现(C++ 代码):
```
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* curr = head;
while (curr != NULL) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
```
其中,ListNode 是链表节点的结构体,包含一个值 val 和一个指向下一个节点的指针 next。head 是链表的头节点指针。算法的时间复杂度为 O(n),其中 n 是链表的长度。
设计一个算法,将链表中所有结点的链接方向“原地”逆转,即要求仅利用原表的存储空间,换句话说,要求算法的空间复杂度为O(1)
可以采用迭代的方式来原地逆转链表,具体实现如下:
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;
}
```