题解 | #牛群排列去重#

/**
 * 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，即为所求