根据一个递增的整数序列构造有序单链表,删除其中的重复元素
时间: 2023-04-27 18:03:28 浏览: 174
最长递增子序列(LIS)问题是一个经典的动态规划问题 给定一个数组,我们要找到其中最长的严格递增子序列的长度
可以按照以下步骤构造有序单链表并删除重复元素:
1. 定义一个链表节点结构体,包含一个整型数据域和一个指向下一个节点的指针域。
2. 读入递增的整数序列,依次创建链表节点,并将节点插入链表中,保证链表始终有序。
3. 遍历链表,对于每个节点,判断它的数据域是否与下一个节点的数据域相同,如果相同,则删除下一个节点,并将当前节点的指针域指向下一个节点的下一个节点。
4. 重复步骤3,直到遍历到链表末尾。
5. 返回删除重复元素后的链表头节点。
具体实现可以参考以下代码:
```c++
#include <iostream>
using namespace std;
// 定义链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL) return NULL;
ListNode* cur = head;
while (cur->next != NULL) {
if (cur->val == cur->next->val) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
} else {
cur = cur->next;
}
}
return head;
}
int main() {
// 读入递增的整数序列
int n;
cin >> n;
ListNode* head = NULL;
for (int i = ; i < n; i++) {
int x;
cin >> x;
ListNode* node = new ListNode(x);
if (head == NULL) {
head = node;
} else {
ListNode* cur = head;
while (cur->next != NULL && cur->next->val < x) {
cur = cur->next;
}
node->next = cur->next;
cur->next = node;
}
}
// 删除重复元素
head = deleteDuplicates(head);
// 输出链表
ListNode* cur = head;
while (cur != NULL) {
cout << cur->val << " ";
cur = cur->next;
}
cout << endl;
return ;
}
```
阅读全文