将单链表倒置,要求只利用原表的存储空间。
时间: 2023-09-25 09:06:29 浏览: 266
### 回答1:
单链表的倒置可以使用三个指针分别指向当前节点、前一个节点和后一个节点,然后依次将当前节点的 next 指针指向前一个节点,再将三个指针向后移动一个节点,直到当前节点指向 NULL。
具体实现步骤如下:
1. 定义三个指针 prev、cur、next,分别指向前一个节点、当前节点和后一个节点,初始时 prev 和 cur 分别指向 NULL 和头节点。
2. 遍历链表,每次将当前节点的 next 指针指向前一个节点,然后将三个指针向后移动一个节点。
3. 最后将头节点指向倒置后的链表的第一个节点,即将原链表的尾节点变成新链表的头节点。
代码实现如下:
```c++
void reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* cur = head;
ListNode* next = NULL;
while (cur != NULL) {
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
head = prev;
}
```
### 回答2:
将单链表倒置的方法中,有一种可以只利用原表的存储空间,即通过改变指针的指向,实现链表的倒置。
下面是具体的步骤:
1. 首先,定义三个指针:pre, cur, next,分别初始化为NULL, head, NULL。pre用于存储前一个节点的指针,cur用于存储当前节点的指针,next用于存储下一个节点的指针。
2. 接着,开始将链表倒置。遍历链表,将cur指针指向的节点的next指针指向pre指针所指向的节点。
```
next = cur->next; // 先存储下一个节点的指针
cur->next = pre; // 当前节点的next指针指向前一个节点
```
3. 然后,将pre指针指向当前节点,cur指针指向下一个节点,继续遍历链表。
```
pre = cur; // 移动pre指针到当前节点
cur = next; // 移动cur指针到下一个节点
```
4. 最后,重复步骤2和3,直到遍历完整个链表。此时,pre指针将指向原链表的最后一个节点,即倒置后链表的头节点。
5. 最后需要将原链表的头节点指向倒置后的头节点。可以通过传入一个指向头指针的指针的方式,将倒置后链表的头指针返回给调用者。
```
*head = pre; // 将头指针指向倒置后的头节点
```
通过以上步骤,我们可以实现将单链表倒置,并且只利用原表的存储空间。
### 回答3:
要将单链表倒置,可以按照以下步骤进行操作,同时满足只利用原表的存储空间的要求。
1. 定义三个指针pre、cur和next,分别表示当前节点、当前节点的前一个节点和当前节点的后一个节点。
2. 初始化pre为NULL,cur为链表的头节点。
3. 对于每个节点cur,进行以下操作:
1) 将当前节点的后一个节点保存到next指针中。
2) 将当前节点的next指针指向pre(即将当前节点的指针方向反转)。
3) 将pre指针指向当前节点,cur指针指向next节点。
4. 当遍历完所有节点后,将链表的头节点指向pre,即为倒置后的链表头节点。
下面是具体的实现代码:
```c
void reverseLinkedList(Node* head) {
Node* pre = NULL;
Node* cur = head;
Node* next = NULL;
while(cur != NULL) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
head = pre;
}
```
这样就可以将单链表倒置,并且满足只利用原表的存储空间的要求。
阅读全文