题解 | #牛群排列去重#
牛群排列去重
https://www.nowcoder.com/practice/8cabda340ac6461984ef9a1ad66915e4
解题思路
- 先判断空链表的情况;
- 定义三个变量,分别指向头结点pre,pre的下一个元素cur,cur的下一个元素next;
- 遍历链表,当cur指向的值等于pre指向的值时,则将pre的next指向next变量;
- 否则的话,pre指向其下一个元素;
- 移动cur和next的指针至下一个。
代码
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
ListNode* deleteDuplicates(ListNode* head) {
// 判断空链表的情况
if (head == nullptr)
{
return head;
}
ListNode* pre = head, *cur = pre->next, *next = cur->next;
//可能需要删除结尾,所以结束标志为cur
while (cur)
{
if(cur->val == pre->val)
{
pre->next = next;
// free(cur);
}
else
{
pre = pre->next;
}
cur = cur->next;
next = next->next;
}
return head;
}
};
时间复杂度
- 时间复杂度:
;
- 空间复杂度:
。