154-删除链表中重复元素(只保留出现一次的元素)

Love The Way You Lie 2023-01-11 09:21 130阅读 0赞

**题目如下：**  
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:  
输入: 1->2->3->3->4->4->5  
输出: 1->2->5

示例 2:  
输入: 1->1->1->2->3  
输出: 2->3

## 解题方法1 ##

1、为了考虑特殊情况，比如1->1-> 2-> 3 这种情况，第一个节点会被删除，所以我们需引入一个哑节点node  
node->next = head;//新结点的next指向head  
2、定义一个p指针指向传入链表的头结点  
3、定义一个q指针指向新结点node  
4、如果遇到连续重复元素，q不动，p一直往后走，走到连续重复元素的最后一个元素结点。 q->next = p->next;//将有重复的值的元素都跳过,然后p=p->next;继续寻找连续重复元素。  
如果没有遇到连续重复元素，则q=p;p=p->next;

ListNode *deleteDuplicates(ListNode *head)
    {
        
        if (head == NULL || head->next == NULL)
        {
        
            return head;
        }
        ListNode *node = new ListNode(0);//申请一个新的结点 
        node->next = head;//新结点的next指向head 
    	 
        ListNode *p = head;
        ListNode *q = node;
        while (p != NULL && p->next != NULL)
        {
        
            if (p->val != p->next->val)//值不相等，p,q一起往后走 
            {
        
                q = p;
            }
            else//值相等
            {
        
                while (p->next != NULL && p->val == p->next->val)
                {
        
                    p = p->next;
                }
                q->next = p->next;//将有重复的值的元素都跳过 
            }
            p = p->next;
        }
        return node->next;//返回处理好的新链表的头结点 
    }

代码演示图如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]

## 解题方法2 ##

**递归方法解决**  
1、如果节点为NULL，或者节点的下一个为NULL，那么直接返回这个节点  
2、如果节点当前元素和下一个元素不相等，那么递归去判断head->next  
3、到这一步，说明当前元素和下一个元素相等，那么跳过所有相等的元素，再去递归判断跳过节点的下一个节点

//递归版本实现
    ListNode *deleteDuplicates(ListNode *head)
    {
        
        if (head == NULL || head->next == NULL)
            return head;
        if(head->val != head->next->val)
        {
        
            head->next = deleteDuplicates(head->next);
            return head;
        }
        while(head!=NULL && head->next != NULL && head->val == head->next->val)
            head = head->next;
        if(NULL == head || NULL == head->next)
            return NULL; 
        return deleteDuplicates(head->next);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/d0879b3fa96145189fd975aa22371885.png