请根据输入的逆序数据采用头插法创建一个单链表,然后删除相同的数据,仅保留一个。
时间: 2024-02-01 08:16:51 浏览: 70
头插法建立单链表
好的,我来给你讲解一下如何用头插法创建单链表,并删除相同的数据。
首先,头插法是指将新节点插入到链表的头部,也就是链表的第一个位置。使用头插法可以使得链表的插入操作时间复杂度为O(1)。
接下来,我们来看一下用头插法创建单链表的具体步骤:
1. 定义一个头指针head,初始值为NULL。
2. 读入逆序数据,每读入一个数据就创建一个新节点,并将该节点插入到链表的头部。
3. 将新节点的next指针指向head。
4. 将head指向新节点。
下面是用头插法创建单链表的示例代码:
```c++
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* createList() {
ListNode *head = NULL;
int x;
while (cin >> x) {
ListNode *node = new ListNode(x);
node->next = head;
head = node;
}
return head;
}
```
接下来,我们来看一下如何删除相同的数据,仅保留一个。具体步骤如下:
1. 定义两个指针p和q,初始值分别为head和head->next。
2. 如果p->val等于q->val,则将q从链表中删除,并释放q的内存,然后将q指向p的下一个节点。
3. 如果p->val不等于q->val,则将p和q都向后移动一个节点。
下面是删除相同的数据的示例代码:
```c++
void removeDuplicates(ListNode *head) {
ListNode *p = head, *q = head->next;
while (q) {
if (p->val == q->val) {
p->next = q->next;
delete q;
q = p->next;
} else {
p = q;
q = q->next;
}
}
}
```
最后,我们来看一下完整的程序代码:
```c++
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* createList() {
ListNode *head = NULL;
int x;
while (cin >> x) {
ListNode *node = new ListNode(x);
node->next = head;
head = node;
}
return head;
}
void removeDuplicates(ListNode *head) {
ListNode *p = head, *q = head->next;
while (q) {
if (p->val == q->val) {
p->next = q->next;
delete q;
q = p->next;
} else {
p = q;
q = q->next;
}
}
}
void printList(ListNode *head) {
ListNode *p = head;
while (p) {
cout << p->val << " ";
p = p->next;
}
cout << endl;
}
int main() {
ListNode *head = createList();
removeDuplicates(head);
printList(head);
return 0;
}
```
希望能对你有所帮助!
阅读全文