如何将带头结点的单链表就地逆置
时间: 2024-05-03 11:16:49 浏览: 133
将带头结点的单链表就地逆置的方法如下:
1. 定义三个指针:pre指向当前节点的前一个节点,cur指向当前节点,next指向当前节点的后一个节点。
2. 将头结点的next指针置为NULL,防止形成环,同时将cur指向头结点的下一个节点。
3. 遍历链表,每次将cur的next指针指向pre,然后将pre、cur、next三个指针分别向后移动一个节点,直到遍历到链表尾部。
4. 最后将头结点的next指针指向pre,链表就地逆置完成。
以下是带头结点的单链表就地逆置的C++代码实现:
```c++
void reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return;
}
ListNode* pre = NULL;
ListNode* cur = head->next;
ListNode* next = NULL;
head->next = NULL; // 防止形成环
while (cur != NULL) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
head->next = pre; // 将头结点的next指针指向pre
}
```
相关问题
带头结点单链表就地逆置
很高兴为您解答关于带头结点单链表就地逆置的问题。带头结点单链表的就地逆置可以通过从首节点开始反转每一个节点的指向,直到链表末尾完成。这里给出一个简单实现的C++代码:
```C++
#include<iostream>
using namespace std;
class ListNode{
public:
int val;
ListNode* next;
ListNode(){}
ListNode(int x): val(x), next(NULL){}
};
ListNode* reverseList(ListNode* head){
if(head==NULL || head->next==NULL) return head;
ListNode* pre = head;
ListNode* cur = head->next;
ListNode* nxt;
pre->next = NULL;
while(cur!=NULL){
nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
int main(){
int n;
cin>>n;
ListNode* head = new ListNode(0);
ListNode* p = head;
for(int i=0;i<n;i++){
int x; cin>>x;
ListNode* node = new ListNode(x);
p->next = node;
p = p->next;
}
head = reverseList(head);
p = head->next;
while(p!=NULL){
cout<<p->val<<" ";
p = p->next;
}
cout<<endl;
return 0;
}
```
该程序首先定义了一个ListNode类作为单链表的节点,然后定义了一个reverseList函数对带头结点的链表进行就地逆置。在main函数中,程序首先读入链表的长度n以及每个节点的值,然后通过一个循环将链表构建完成。接下来,我们对链表进行就地逆置,最后按照逆序输出每个节点的值。希望我的回答能够帮助到您,如有疑问,请随时追问。
带头结点的单链表就地逆置
算法思路:
1. 定义三个指针prev、cur、next,分别指向头结点、头结点的下一个节点和下一个节点的下一个节点。
2. 将头结点的指针域置为NULL,表示反转后的链表末尾节点。
3. 循环遍历单链表,直到cur指向NULL,每次循环,将cur的指针域指向prev,表示将当前节点插入到反转后链表的头部。
4. 将prev指向cur,cur指向next,next指向next的下一个节点,继续遍历单链表。
5. 最后将头结点的指针域指向prev,完成链表的就地反转。
C++代码实现:
```c++
void reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return;
}
ListNode *prev = head, *cur = head->next, *next = cur->next;
prev->next = NULL;
while (cur != NULL) {
cur->next = prev;
prev = cur;
cur = next;
if (next != NULL) {
next = next->next;
}
}
head->next = prev;
}
```
阅读全文