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

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

234a3459c2b1059c64f05e2ec48d0995.png

问题描述

来源：LeetCode第82题

难度：中等

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

示例1：

13180c0b046d30e6744eb587ee192bde.jpeg

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

输出：[1,2,5]

示例2：

780cda8dc5b3d1f5938ac857e866ab76.jpeg

输入：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);
    }
};

d982194634e0d3a86c8883b7d75996e3.gif

笔者简介

博哥，真名：王一博，毕业十多年，《算法秘籍》作者，专注于数据结构和算法的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解700多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以下载我整理的1000多页的PDF算法文档。