设单链表以非递减有序排列,设计算法实现在单链表中删除值相同的多余结点
时间: 2023-04-24 13:05:14 浏览: 163
算法步骤如下:
1. 定义两个指针p和q,p指向当前结点,q指向下一个结点。
2. 如果p结点的值等于q结点的值,则将q结点从链表中删除,并释放其内存空间。
3. 如果p结点的值不等于q结点的值,则将p指针后移一位,继续比较下一个结点。
4. 重复步骤2和3,直到p指针指向链表的最后一个结点。
5. 返回删除多余结点后的链表。
代码实现如下:
```
void removeDuplicates(ListNode* head) {
ListNode* p = head;
while (p != NULL && p->next != NULL) {
if (p->val == p->next->val) {
ListNode* q = p->next;
p->next = q->next;
delete q;
} else {
p = p->next;
}
}
}
```
相关问题
设单链表以非递减有序排列,设计算法实现在单链表中删去值相同的多余结点,c++实现
```c
#include <stdio.h>
#include <stdlib.h>
// 定义单链表结构体
typedef struct node {
int data; // 数据域
struct node *next; // 指针域
} Node, *LinkList;
// 创建单链表
LinkList createList(int n) {
LinkList head = (LinkList)malloc(sizeof(Node)); // 创建头结点
head->next = NULL; // 头结点的指针域初始化为 NULL
LinkList p, q;
q = head;
for (int i = 0; i < n; i++) {
p = (LinkList)malloc(sizeof(Node)); // 创建新结点
scanf("%d", &p->data); // 输入新结点的值
p->next = NULL; // 新结点的指针域初始化为 NULL
q->next = p; // 前驱结点的指针域指向新结点
q = p; // 前驱结点移动到新结点
}
return head;
}
// 删除重复结点
void deleteDuplicates(LinkList L) {
LinkList p = L->next, q; // p 指向第一个结点,q 指向 p 的前驱结点
while (p != NULL) {
q = p;
while (q->next != NULL && q->next->data == p->data) {
q = q->next; // 找到与 p 值相同的最后一个结点
}
if (q != p) { // 如果存在与 p 值相同的结点
p->next = q->next; // 将 p 的后继指向 q 的后继
LinkList temp;
while (p != q) { // 释放 p 到 q 之间的结点
temp = p;
p = p->next;
free(temp);
}
free(q); // 释放 q 结点
} else {
p = p->next; // 没有与 p 值相同的结点,p 后移一位
}
}
}
// 输出单链表
void printList(LinkList L) {
LinkList p = L->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main() {
int n;
printf("请输入单链表长度:");
scanf("%d", &n);
LinkList L = createList(n);
printf("原始单链表:");
printList(L);
deleteDuplicates(L);
printf("删除重复结点后的单链表:");
printList(L);
return 0;
}
```
设计一个算法,在非递减有序的带头结点的单链表中删除值相同的多余结点。
算法步骤如下:
1. 定义两个指针p和q,p指向头结点,q指向第一个非头结点。
2. 循环遍历链表,如果p的值等于q的值,则删除q结点,否则p和q同时后移一个结点。
3. 循环结束后,返回头结点即可。
代码实现如下:
```
ListNode* deleteDuplicates(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* p = head;
ListNode* q = head->next;
while (q != nullptr) {
if (p->val == q->val) {
p->next = q->next;
delete q;
q = p->next;
} else {
p = p->next;
q = q->next;
}
}
return head;
}
```
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)