题解 | #牛群排列去重#
牛群排列去重
https://www.nowcoder.com/practice/8cabda340ac6461984ef9a1ad66915e4
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @return ListNode类
*/
struct ListNode* deleteDuplicates(struct ListNode* head ) {
// write code here
struct ListNode* pre = head, *cur = pre->next;
//判断空链表
if(head==NULL)
{
return head;
}
while(cur)
{
if(pre->val == cur->val)
{
if((cur->next == NULL)&& (pre->val == cur->val))
{
pre->next = NULL;
}
cur = cur->next;
}
else
{
pre->next = cur;
pre = cur;
cur = cur->next;
}
}
return head;
}
1.考察的知识点：单链表
2.编程语言：C
3.解题思路：首先进行空链表直接返回的输出；
以1 2 2 2 2 3 3 4 5 5为例，仍然可用pre指针和cur指针遍历对比解决该问题。
首先确定遍历结束条件，在循环中每次cur都会向后移动，即cur = cur->next; 结束条件确定为cur==NULL
然后判断共有2种情况：
第一种情况：当pre的值==cur的值，以2 2 2 2为例 ，pre指向第一个2，cur指向第二个2，
为了删除多余的重复数字，可以考虑
(1)每次都删除cur
(2)找到所有的2直接删除，此时条件变为pre的值！=cur的值，在情况二中进行更新处理即可。本代码选用(2)。
最后，在第一种情况下，末尾需要特殊处理，pre指向5，cur指向末尾处重复的5，应当直接将pre->next置空。
第二种情况：当pre的值！=cur的值，首先将pre->next直接指向cur对情况一中的(2)更新处理；
然后cur和pre都向后移动
最后直接返回head，即为所求
#面试高频TOP202##薅羊毛##菜鸟进化##2023-8-3学习2#
查看10道真题和解析