c语言 在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留。 例如,链表1->2->3->3->4->4->5 处理后为 1->2->3->4->5 输入说明 链表的元素序列 输出说明 删除重复元素后的链表元素序列
时间: 2024-06-04 17:13:10 浏览: 12
可以使用双指针的方法来查找并删除重复的结点。定义一个指针p指向当前不重复的结点,另一个指针q从p的下一个结点开始向后遍历,如果q指向的结点与p指向的结点相同,则不断向后移动q指针直到找到一个不同的结点,然后将p的next指针指向该结点。最后返回链表的头结点即可。
C++代码如下:
ListNode* deleteDuplicates(ListNode* head) {
if (!head) return head;
ListNode *dummy = new ListNode(-1), *p = dummy;
dummy->next = head;
while (p->next) {
ListNode *q = p->next;
while (q && q->val == p->next->val) {
q = q->next;
}
if (q != p->next->next) {
p->next = q;
} else {
p = p->next;
}
}
return dummy->next;
}
这段代码的时间复杂度是O(n),其中n是链表的长度。
相关问题
用C语言删除一个链表中的重复结点
可以使用双重循环来遍历链表,比较每一个节点与后面节点的值是否相同,如果相同则删除后面的节点。具体实现可以参考以下代码:
```c
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* deleteDuplicates(struct ListNode* head){
if(head == NULL) return head;
struct ListNode* cur = head;
while(cur != NULL){
struct ListNode* tmp = cur;
while(tmp->next != NULL){
if(tmp->next->val == cur->val){
tmp->next = tmp->next->next;
}else{
tmp = tmp->next;
}
}
cur = cur->next;
}
return head;
}
```
这段代码中,我们使用了两个指针,`cur`指向当前节点,`tmp`指向当前节点的后面一个节点。如果`tmp`的值与`cur`相同,则删除节点;否则`tmp`指向下一个节点,直到链表末尾。接着,`cur`指向下一个节点,继续遍历链表,直至遍历完整个链表。最后返回链表头结点`head`即可。
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留。用完整的C语言程序实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* deleteDuplication(struct ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
struct ListNode* preNode = NULL;
struct ListNode* curNode = head;
while (curNode) {
struct ListNode* nextNode = curNode->next;
int flag = 0;
while (nextNode && nextNode->val == curNode->val) {
flag = 1;
nextNode = nextNode->next;
}
if (flag == 1) {
if (preNode == NULL) {
head = nextNode;
} else {
preNode->next = nextNode;
}
curNode = nextNode;
} else {
preNode = curNode;
curNode = curNode->next;
}
}
return head;
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)