[数据结构与算法]LeetCode每日一题题解：82. 删除排序链表中的重复元素 II-题解-python && C++源代码

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

难度中等827收藏分享切换为英文接收动态反馈

给定一个已排序的链表的头?head?，?删除原始链表中所有重复数字的节点，只留下不同的数字?。返回?已排序的链表?。

示例 1：

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：

输入：head = [1,1,1,2,3]
输出：[2,3]

提示：

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

题目思路：

因为链表的头结点可能被删除，因此我们需要加一个哑结点ads，然后我们在遍历的过程中可能会遇到ans.next?和ans.next.next为0的情况因此我们需要将这个作为判断条件，当我们发现了一个重复的X值后，我们需要重复往后判断，将所有等于x的值全部删掉因此本题是排序好的，所有相同的值是在一起的所有这样操作就行。最后输出哑结点的next即可。

Python代码：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        if head is None:  #如果链表为空节点，则输出错误
            return head
        
        ads = ListNode(0 , head)  #构建一个哑结点，因为头结点可能被删除
        ans = ads
        while ans.next and ans.next.next:      
            if ans.next.val == ans.next.next.val:
                a = ans.next.val
                while ans.next and ans.next.val == a:
                    ans.next = ans.next.next
                
            else:
                ans = ans.next
        return ads.next

C++代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr){
            return head;
        }
        ListNode*ads = new ListNode(0 , head); //构建哑结点
        ListNode*ans = ads;
        int a = 0;
        while(ans->next && ans->next->next){
            if (ans->next->val == ans->next->next->val){
                a = ans->next->val;
                while (ans->next && ans->next->val == a){
                    ans->next = ans->next->next;
                }

            }
            else{
                ans = ans->next;
            }
        }
        return ads->next;

    }
};