在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留。例如,链表1->2->3->3->4->4->5处理后为1->2->3->4->5
时间: 2024-06-03 17:09:06 浏览: 17
好的,这是一个关于链表的问题。这个问题可以使用双指针来解决。具体的做法是,我们定义两个指针,一个慢指针p,一个快指针q,并且让它们都从链表的头结点开始遍历。当p指向的节点与q指向的节点相同时,我们就让q一直向后遍历,直到q指向的节点与p指向的节点不同。此时,我们就可以将p的next指向q,然后让p向后移动一位,继续遍历整个链表。最后,返回处理后的链表即可。
笑话时间:为什么程序员总是把0当成1?因为他们从0开始数!
相关问题
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留。
例如,链表1->2->3->3->4->4->5 处理后为 1->2->5。
算法1:双指针
思路:
- 定义一个前节点和当前节点
- 当前节点和后面的节点比较,如果相等,就删除后面的节点,如果不相等,前节点和当前节点同时向后移动
时间复杂度:O(n)
空间复杂度:O(1)
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* dummy = new ListNode(-1);
dummy->next = head;
ListNode* pre = dummy;
ListNode* cur = head;
while (cur != nullptr) {
if (cur->next != nullptr && cur->val == cur->next->val) {
while (cur->next != nullptr && cur->val == cur->next->val) {
cur = cur->next;
}
pre->next = cur->next;
} else {
pre = pre->next;
}
cur = cur->next;
}
return dummy->next;
}
};
在一个排序的链表中,存在重复的结点,请删除该链表中重复的结点,重复的结点不保留。用完整的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)
![md](https://img-home.csdnimg.cn/images/20210720083646.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)