设计一个算法,在非递减有序的带头结点的单链表中删除值相同的多余结点。
时间: 2023-04-22 21:00:37 浏览: 87
算法步骤如下:
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;
}
```
相关问题
设单链表以非递减有序排列,设计算法实现在单链表中删除值相同的多余结点
算法步骤如下:
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;
}
}
}
```
设计一个算法,删除一个带头结点单链表中所有值为x的结点。
可以使用双指针法,一个指针指向当前结点,另一个指针指向当前结点的前一个结点。遍历整个链表,如果当前结点的值等于x,则将前一个结点的next指针指向当前结点的next指针,然后删除当前结点。如果当前结点的值不等于x,则将两个指针都向后移动一位。最后返回头结点即可。
以下是示例代码:
```
void deleteNode(ListNode* head, int x) {
ListNode* prev = head;
ListNode* curr = head->next;
while (curr != nullptr) {
if (curr->val == x) {
prev->next = curr->next;
delete curr;
curr = prev->next;
} else {
prev = curr;
curr = curr->next;
}
}
}
```
相关推荐
![](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)