实现删除单链表中值相同的多余结点的算法
时间: 2023-04-15 08:04:04 浏览: 172
可以使用双重循环遍历单链表,对于每个结点,再遍历其后续结点,如果有值相同的结点,则将其删除。具体实现如下:
1. 定义两个指针p和q,初始时p指向链表的头结点,q指向p的下一个结点。
2. 循环遍历链表,对于每个结点p,再循环遍历其后续结点,对于每个结点q,如果q的值与p相同,则将q从链表中删除。
3. 删除结点q的方法为:将p的next指针指向q的下一个结点,然后释放q的内存空间。
4. 如果q的值与p不同,则将q指针向后移动一位,继续循环遍历。
5. 当q指针移动到链表的末尾时,将p指针向后移动一位,继续循环遍历。
6. 当p指针移动到链表的末尾时,算法结束。
完整代码如下:
void removeDuplicates(ListNode* head) {
ListNode* p = head;
while (p != nullptr) {
ListNode* q = p->next;
while (q != nullptr) {
if (q->val == p->val) {
p->next = q->next;
delete q;
q = p->next;
} else {
q = q->next;
}
}
p = p->next;
}
}
相关问题
c语言:写一算法将单链表中值重复的结点删除
算法如下:
1. 定义两个指针:p和q,p指向当前结点,q指向p的下一个结点。
2. 当p不为空时,执行以下循环:
a. 如果p的值与q的值相等,则删除q结点。
b. 否则,将p指向q,q指向q的下一个结点。
c. 如果q为空,则将p的下一个结点设为NULL,结束循环。
3. 返回被删除结点的个数。
C语言代码实现如下:
```
int removeDuplicateNodes(Node* head){
int count = 0;
Node *p = head, *q;
while(p != NULL){
q = p->next;
while(q != NULL){
if(p->data == q->data){
p->next = q->next;
free(q);
q = p->next;
count++;
}
else{
p = q;
q = q->next;
}
}
p->next = NULL;
p = p->next;
}
return count;
}
```
其中,Node为链表结点的结构体,包含数据域data和指向下一个结点的指针next。
删除带头结点的单链表中值最大的结点
如果链表为空或者只有一个结点,那么就没有结点可以删除,直接返回链表头节点即可。
如果链表有多结点,我们需要先找到值最大结点,然后将其从链表中。具体步骤如下:
1. 定义一个指针变量 `prev` 指向头结点的前一个结点,指针变量 `p 指向头结点;
2. 定义一个变量 `max_value` 保存当前找到的最大值,初始化为头结点的值;
3. 遍历链表,如果当前结点的值大于 `max_value`,则更新 `max_value` 和指向最大值结点的指针变量 `max_node`;
4. 遍历完成后,如果 `max_node` 指向的是头结点,则直接删除头结点,否则删除 `max_node`;
5. 返回链表头节点。
具体实现如下(假设链表中存储的是整数):
```c++
ListNode* deleteMaxNode(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* prev = head;
ListNode* p = head->next;
ListNode* max_node = head;
int max_value = head->val;
while (p != nullptr) {
if (p->val > max_value) {
max_value = p->val;
max_node = p;
}
prev = p;
p = p->next;
}
if (max_node == head) {
head = head->next;
} else {
prev->next = max_node->next;
}
delete max_node;
return head;
}
```