美团实习二面原题，网友直呼太难。。。

将 脚本之家 设为“星标⭐”第一时间收到文章更新本文经数据结构和算法（id:sjjghsf）授权转载

今天这题是LeetCode的第82题：删除排序链表中的重复元素 II，一网友在美团面试的时候遇到这道题，不过很遗憾的是该网友没有做出来，其实这是一道中等难度的题，还不算太难。除了美团以外，字节，腾讯也都考过，我们来看下。

问题描述

来源：LeetCode第82题
难度：中等
给定一个已排序的链表的头 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

• 题目数据保证链表已经按升序 排列

问题分析

这题让把链表中重复的节点全部给删除，因为题中说了链表是排序的，所以重复的节点肯定是挨着的。对于每一个节点都要与他后面的节点比较，如果相同就要把它后面的给删除，接着继续比较。

这里要注意如果有相同的，不要把相同节点的第一个节点给忘了，我们可以使用递归的方式来解决，代码如下。

JAVA：

public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null)
        return head;
    if (head.val != head.next.val) {
        // 如果当前节点和下一个节点的值不相同，不需要删除
        head.next = deleteDuplicates(head.next);
        return head;
    } else {
        // 如果当前节点和下一个节点的值相同，说明出现了重复的，
        // 把重复的全部给删除。
        while (head.next != null && head.val == head.next.val)
            head = head.next;
        return deleteDuplicates(head.next);
    }
}

C++：

public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        if (head->val != head->next->val) {
            // 如果当前节点和下一个节点的值不相同，不需要删除
            head->next = deleteDuplicates(head->next);
            return head;
        } else {
            // 如果当前节点和下一个节点的值相同，说明出现了重复的，
            // 把重复的全部给删除。
            while (head->next != nullptr && head->val == head->next->val)
                head = head->next;
            return deleteDuplicates(head->next);
        }
    }

C：

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

struct ListNode* deleteDuplicates(struct ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;
    if (head->val != head->next->val) {
        // 如果当前节点和下一个节点的值不相同，不需要删除
        head->next = deleteDuplicates(head->next);
        return head;
    } else {
        // 如果当前节点和下一个节点的值相同，说明出现了重复的，
        // 把重复的全部给删除。
        while (head->next != NULL && head->val == head->next->val)
            head = head->next;
        return deleteDuplicates(head->next);
    }
}

Python：

def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if not head or not head.next:
        return head
    if head.val != head.next.val:
        # 如果当前节点和下一个节点的值不相同，不需要删除
        head.next = self.deleteDuplicates(head.next)
        return head
    else:
        # 如果当前节点和下一个节点的值相同，说明出现了重复的，
        # 把重复的全部给删除。
        while head.next and head.val == head.next.val:
            head = head.next
        return self.deleteDuplicates(head.next)

JS：

var deleteDuplicates = function (head) {
    if (!head || !head.next)
        return head;
    if (head.val !== head.next.val) {
        // 如果当前节点和下一个节点的值不相同，不需要删除
        head.next = deleteDuplicates(head.next);
        return head;
    } else {
        // 如果当前节点和下一个节点的值相同，说明出现了重复的，
        // 把重复的全部给删除。
        while (head.next != null && head.val === head.next.val)
            head = head.next;
        return deleteDuplicates(head.next);
    }
};

  推荐阅读：