《剑指offer刷题笔记》17、删除链表中重复的节点【c++详细题解】

女爷i 2021-07-24 20:30 317阅读 0赞

### **题目** ###

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留。

**样例1**

输入：1->2->3->3->4->4->5
    
    输出：1->2->5

**样例2**

输入：1->1->1->2->3
    
    输出：2->3

### **思路** ###

**(线性扫描)** O ( n ) O(n) O(n)  
为了方便处理边界情况，我们定义一个虚拟元素 d u m m y dummy dummy指向链表头节点。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70][]

然后从前往后扫描整个链表，每次扫描元素相同的一段，如果这段中的元素个数多于 1 1 1个，则将整段元素直接删除。

本题的难点是判断哪些元素是重复以及如何跨越重复元素连接到下一个重复元素处。

我们可以定义两个指针，`p`和`q`，让`p`指针指向我们一段重复的节点的上一个节点，`q`指向这段重复节点的的下一个节点。这样p和q指针中间的那一段就是重复的元素，我们执行`p->next=q`将其删除即可。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1][]

**如何让p和q可以指向上述的位置呢？**

1、刚开始时`q`为`p`的下一个节点(`q = p->next`)

2、如果`p`的下个节点的值和`q`节点的值相等(`p->next->val == q->val`)，我们就让`q`指针后移一位(`q = q->next`)，直到不相等为止。最后p和q指针中间的那一段就是重复的元素。

3、我们将`p->next = q`，就将中间的重复的一段元素删除去了。但是如果p和q之间只有一个元素(`p->next->next == q`) 说明p和q之间没有重复的一段元素，我们让p指针后移一位，重复上述操作。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 2][]

此图说明p和q之间没有重复的一段元素。

**时间复杂度**  
整个链表只扫描一遍，所以时间复杂度是  O ( n ) O(n) O(n)。

### **代码** ###

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution { 
    public:
        ListNode* deleteDuplication(ListNode* head) { 
            auto dummy = new ListNode(-1);
            dummy->next = head;
    
            auto p = dummy;
            while (p->next) { 
                auto q = p->next;
                while (q && p->next->val == q->val) q = q->next;
    
                if (p->next->next == q) p = p->next;
                else p->next = q;
            }
    
            return dummy->next;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70]: /images/20210724/0e5cfad25cbc4677b35cfeb5760e6859.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 1]: /images/20210724/6021a3a8f64a474f9d26408537a364de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTYyOTI4NQ_size_16_color_FFFFFF_t_70 2]: /images/20210724/6cbd2189854b4ee3b380b200558c6c6e.png