[编程题]删除链表中重复的结点 C语言

删除链表中重复的结点

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

示例1

输入 {1,2,3,3,4,4,5}

输出 {1,2,5}

思路：

prev指向NULL。cur指向首结点。next指向cur的下一个节点。

如果cur和next指向节点的值不相等。就一起往后走。直到cur->val 等于 next->val

if(cur->val != next->val) 
            {
          
   
                prev = cur;
                cur = next;
                next = next->next;
            }

此时让next单独向后走，直到cur的val不等于next的val，next停止。再让prev的next指向next。

while(cur->val == next->val)
                {
          
   
                    next = next->next;
                }  
                    prev->next = next;

然后让cur 移动到next。next向后移动。继续比较。

代码初步实现

ListNode* deleteDuplication(ListNode* pHead) {
          
   
    
        if(pHead == NULL || pHead->next == NULL)
                return pHead;
        
        ListNode* prev = NULL;
        ListNode* cur = pHead;
        ListNode* next = pHead->next;

        
        while(next)
        {
          
   
            if(cur->val != next->val) 
            {
          
   
                prev = cur;
                cur = next;
                next = next->next;
            }
            else
            {
          
   
                while( cur->val == next->val)
                {
          
   
                    next=next->next;
                }
           
                prev->next = next;
               
                cur = next;
                next = next->next;
            }
        }
        
        return pHead;
    }

还要考虑以下情况

如果链表头为重复元素，此时prev还是NULL。对空指针解引用操作。

修改

if(prev) //不为空就向后移动
 	 prev->next = next;
else //为空说明头部都是重复元素，直接改变链表头。
     pHead = next;

当链表尾部为重复元素

此时next已经为NULL。

修改后

ListNode* deleteDuplication(ListNode* pHead) {
          
   
    
        if(pHead == NULL || pHead->next == NULL)
                return pHead;
        
        ListNode* prev = NULL;
        ListNode* cur = pHead;
        ListNode* next = pHead->next;

        while(next)
        {
          
   
            if(cur->val != next->val) 
            {
          
   
                prev = cur;
                cur = next;
                next = next->next;
            }
            else
            {
          
   
                while(next && cur->val == next->val)//注意空指针
                {
          
   
                    next=next->next;
                }
                
                if(prev)
                    prev->next = next;
                else
                    pHead = next;
                
                cur = next;
                
                if(next) //如果为空停止移动
                    next = next->next;
            }      
        }
        
        return pHead;
    }