带头结点单链表和带表头节点单链表是一个概念吗?
时间: 2023-06-12 07:01:54 浏览: 59
带头节点单链表和带表头节点单链表是不同的概念。带头节点单链表是在原单链表的基础上,增加一个头节点,用来存放链表长度等辅助信息,也可以作为哨兵节点,方便进行链表操作。而带表头节点单链表则是在原单链表的基础上,将第一个节点作为表头节点,用来存放链表长度等辅助信息,但不是哨兵节点。两者的区别在于节点的位置和用途。
相关问题
建立两个带头结点单链表
好的,我来给你写一下建立两个带头结点单链表的代码。这里假设链表中存储的元素为整型数。
```c++
#include <iostream>
using namespace std;
struct ListNode{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode *createList(){
ListNode *head = new ListNode(0); // 头结点
ListNode *cur = head;
int n;
cout << "输入链表长度:";
cin >> n;
for(int i=0; i<n; i++){
int x;
cin >> x;
ListNode *node = new ListNode(x);
cur->next = node;
cur = node;
}
return head;
}
int main(){
ListNode *list1 = createList();
ListNode *list2 = createList();
return 0;
}
```
这个程序会提示你输入两个链表的长度,然后分别输入每一个节点的值,最后返回两个带头结点的链表头指针 list1 和 list2。
带表头结点单链表的逆置
对于带头结点的单链表,我们可以从头结点的下一个节点开始,依次将每个节点插入到头结点之后,直到所有节点都被插入完成,最后再将头结点的next指针指向新的第一个节点即可。
具体实现如下:
```c++
void reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return;
}
ListNode* p = head->next;
ListNode* q = p->next;
while (q != nullptr) {
p->next = q->next;
q->next = head->next;
head->next = q;
q = p->next;
}
}
```