设计一个算法,将链表中所有节点的链接方向“原地”逆转,即要求仅利用原表的存储空间。即要求算法的空间复杂度为O(1)。
时间: 2023-05-21 14:07:17 浏览: 136
这个问题需要用到三个指针:p、q、r,p指向当前节点,q指向p的下一个节点,r指向q的下一个节点。每次将q的指针指向p,然后依次移动p、q、r指针,直到r指针为NULL为止。具体算法如下:
```
void reverseList(Node* head) {
Node *p = head, *q = head->next, *r = q->next;
p->next = NULL;
while (r != NULL) {
q->next = p;
p = q;
q = r;
r = r->next;
}
q->next = p;
}
```
这样,链表中所有节点的链接方向就会被“原地”逆转,且空间复杂度为O(1)。
阅读全文