带头结点的单链表的逆置
时间: 2024-04-06 13:27:45 浏览: 34
带头结点的单链表逆置是指将链表中节点顺序反转,使得原先的尾节点成为新的头节点,原先的头节点成为新的尾节点。下面是带头结点的单链表逆置的步骤:
1. 创建一个新的空链表,即新的头结点。
2. 遍历原链表,从头结点的下一个节点开始,依次将每个节点插入到新链表的头部。
3. 将新链表的头结点指向原链表的尾节点。
4. 将原链表的尾节点指向空。
这样就完成了带头结点的单链表的逆置。
相关问题
带头结点单链表就地逆置
很高兴为您解答关于带头结点单链表就地逆置的问题。带头结点单链表的就地逆置可以通过从首节点开始反转每一个节点的指向,直到链表末尾完成。这里给出一个简单实现的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以及每个节点的值,然后通过一个循环将链表构建完成。接下来,我们对链表进行就地逆置,最后按照逆序输出每个节点的值。希望我的回答能够帮助到您,如有疑问,请随时追问。
带头结点的单链表逆置
以下是带头结点的单链表逆置的 C++ 代码实现:
```cpp
#include <iostream>
using namespace std;
// 定义链表结点
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
// 定义链表逆置函数
ListNode* reverseList(ListNode* head) {
ListNode* prev = NULL;
ListNode* curr = head->next;
while (curr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
head->next = prev;
return head;
}
// 测试
int main() {
ListNode* head = new ListNode(0);
ListNode* p1 = new ListNode(1);
ListNode* p2 = new ListNode(2);
ListNode* p3 = new ListNode(3);
head->next = p1;
p1->next = p2;
p2->next = p3;
cout << "原链表:";
for (ListNode* p = head->next; p; p = p->next) {
cout << p->val << " ";
}
cout << endl;
head = reverseList(head);
cout << "逆置后链表:";
for (ListNode* p = head->next; p; p = p->next) {
cout << p->val << " ";
}
cout << endl;
return 0;
}
```
该代码中,reverseList 函数实现了链表的逆置操作,head 为带头结点的链表头。在逆置过程中,需要用到三个指针 prev、curr 和 next,分别表示前驱结点、当前结点和后继结点。具体实现方式是,每次将 curr 结点的 next 指针指向 prev,然后将 prev、curr 和 next 分别后移一个结点,直到 curr 结点为空。最后将头结点的 next 指针指向逆置后的链表头结点 prev。