设计算法将单链表L就地逆置
时间: 2024-05-09 15:16:45 浏览: 96
单链表的就地逆置可以通过修改节点的指向来实现。具体算法如下:
1. 定义三个指针:prev、curr、next,分别指向前一个节点、当前节点和后一个节点。
2. 初始化prev为NULL,curr为L的头节点。
3. 遍历单链表,重复以下步骤:
1. 将next指针指向curr的下一个节点。
2. 将curr的下一个节点指向prev。
3. 将prev指针指向curr。
4. 将curr指针指向next。
4. 最后将L的头节点指向prev,完成就地逆置。
下面是具体的实现代码:
```python
def reverse_list(head):
prev = None
curr = head
while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next
head = prev
return head
```
需要注意的是,本算法的时间复杂度为O(n),其中n为单链表的长度。
相关问题
设计算法将单链表L就地逆置,即利用原表各结点的空间实现逆置
可以按照以下步骤进行单链表的就地逆置:
1. 定义三个指针:pre、cur、next,分别表示当前节点的前一个节点、当前节点和当前节点的后一个节点。
2. 将 pre 指向 NULL,cur 指向单链表的头结点。
3. 遍历单链表,每遍历一个节点,就将该节点的 next 指针指向 pre,然后依次向后移动 pre、cur 和 next 指针,即:pre = cur,cur = next,next = next->next。
4. 遍历完单链表后,将原头结点的 next 指针置为 NULL,将逆置后的单链表的头结点设为原来的尾节点。
下面是具体的实现代码:
```c++
void reverseList(ListNode* &head) {
if (head == NULL || head->next == NULL) {
return;
}
ListNode *pre = NULL, *cur = head, *next = head->next;
while (next != NULL) {
cur->next = pre;
pre = cur;
cur = next;
next = next->next;
}
cur->next = pre;
head->next = NULL;
head = cur;
}
```
需要注意的是,在函数中需要使用引用来修改头结点,否则逆置后的单链表无法返回给调用者。
设计算法将单链表L就地逆置,即利用原表各结点的空间实现逆置。
可以使用三个指针来实现单链表的就地逆置,具体算法如下:
1. 初始化三个指针:pre指向NULL,cur指向L的头结点,next指向cur的下一个结点。
2. 遍历链表,依次将cur结点的next指向pre结点,然后将pre、cur、next分别后移。具体操作如下:
a. 将cur的next指向pre:cur->next = pre;
b. 将pre、cur、next依次向后移动:pre = cur; cur = next; next = next->next;
3. 遍历完链表后,将原链表的头结点指向逆置后的尾结点。具体操作如下:
a. 将L的头结点指向pre结点:L->next = pre;
最后返回L即可。
下面是C++代码实现:
```c++
void reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head->next;
ListNode* next = cur->next;
while (next != NULL) {
cur->next = pre;
pre = cur;
cur = next;
next = next->next;
}
cur->next = pre;
head->next = cur;
}
```
需要注意的是,这里的head是一个头结点,而不是实际存储数据的第一个结点。在遍历完链表后,head->next指向的就是逆置后的尾结点。
阅读全文