[数据结构与算法]牛客网-NC24 删除有序链表中重复的元素-II

一、题目

二、思路

方法一：用map容器储存每个值，然后遍历map容器，新建值为1的节点
方法二、双指针

• 首先创建一个新节点，新节点指向head，并且定义两个节点，当前节点和前节点

• while循环，当前节点和它的下一个节点不为空。两种情况

  • 当前节点和下一个节点相等，遍历找到第一个不相等的，然后pre指向这个第一个不相等的节点
  • 当前节点和下一个节点相等，pre=当前节点，当前节点=下一个节点

三、代码

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==nullptr || head->next==nullptr)
        {
            return head;
        }
        
        //定义头结点，使判断从第一个开始
        ListNode *node=new ListNode(-1);
        node->next=head;
        
        //定义两个节点
        ListNode *pre=node;
        ListNode *cur=head;
        
        //当前节点和当前节点的下一个节点不为空
        while(cur && cur->next)
        {
            //如果下一个节点和当前节点相同
            if(cur->val==cur->next->val)
            {
                //找到第一个不相等的，即为cur->next
                while(cur->next && cur->val==cur->next->val)
                {
                    cur=cur->next;
                }
                //pre节点指向第一个不相等的
                pre->next=cur->next;
                //当前节点指向不相等的第一个
                cur=cur->next;
            }
            else
            {
                //pre等于当前节点
                pre=cur;
                //当前节点等于下一个
                cur=cur->next;
            }
        }
        return node->next;
    }
};