删除排序链表中的重复元素 II

• 有关题目
• • 题解

题目链接： 删除排序链表中的重复元素 II

有关题目

存在一个按升序排列的链表，给你这个链表的头节点 head ，
请你删除链表中所有存在数字重复情况的节点，只保留原始链表
中 没有重复出现 的数字。

返回同样按升序排列的结果链表。

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序排列

题解

代码一：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* deleteDuplicates(struct ListNode* head){
    if (!head) return NULL;
    struct ListNode* pre = NULL;
    struct ListNode* cur = head;
    while(cur->next)
    {
        //删除的为头节点
        if (head->val == head->next->val)
        {
            while(head->next != NULL && head->val == head->next->val)//head->next != NULL不放在前面就有可能会越界
                head = head->next;
            if (head->next == NULL) return NULL;//通过[1,1]
            head = head->next;//通过[1,1,1,2,2,3,5]
            cur = head;
        }
        else//不是头节点
        {
             if (cur->val == cur->next->val)
            {
                while(cur->next != NULL && cur->val == cur->next->val) 
                    cur = cur->next;
                if (cur->next == NULL) //通过[1,2,2]
                {
                    pre->next = NULL;
                    return head;
                }
                pre->next = cur->next;//通过[1,2,2,3,4]
                cur = pre->next;
            }
            else
            {
                pre = cur;
                cur = cur->next;
            }
        }
    }
    return head;
}

代码二：

由于链表的头节点可能会被删除，因此我们需要额外使用一个哑节点（dummy node)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* deleteDuplicates(struct ListNode* head){
    if (!head) return NULL;
    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));//创建哑节点
    dummy->next = head;//合并出现删除头部的情况

    struct ListNode* cur = dummy;
    while(cur->next && cur->next->next)//通过[null,1,1,2]验证
    {
        if ( cur->next->val == cur->next->next->val)
        {
            int x = cur->next->val;//记录此时相等的值
            while(cur->next && cur->next->val == x)//除去所有x
                cur->next = cur->next->next;
        }
        else
             cur = cur->next;
    }
    return dummy->next;
}