设计一个算法,利用单链表原来的结点空间将一个单链表就地逆转
时间: 2023-04-15 17:01:17 浏览: 104
可以使用三个指针prev、curr、next,分别指向当前结点的前一个结点、当前结点和当前结点的后一个结点。遍历单链表,将当前结点的next指针指向prev,然后依次向后移动三个指针,直到遍历完整个单链表。最后将原来的头结点指向原来的尾结点,即可完成单链表的就地逆转。
具体实现如下:
```
void reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return;
}
ListNode* prev = nullptr;
ListNode* curr = head;
ListNode* next = head->next;
while (next != nullptr) {
curr->next = prev;
prev = curr;
curr = next;
next = next->next;
}
curr->next = prev;
head->next = nullptr;
head = curr;
}
```
其中,head为原来的头结点,prev、curr、next分别为三个指针,初始时prev为nullptr,curr为头结点,next为头结点的下一个结点。在遍历单链表的过程中,将当前结点的next指针指向prev,然后依次向后移动三个指针。最后将原来的头结点指向原来的尾结点,即curr,完成单链表的就地逆转。
阅读全文