其他
美团实习二面原题，网友直呼太难。。。
The following article is from 数据结构和算法 Author 博哥
今天这题是LeetCode的第82题：删除排序链表中的重复元素 II，一网友在美团面试的时候遇到这道题，不过很遗憾的是该网友没有做出来，其实这是一道中等难度的题，还不算太难。除了美团以外，字节，腾讯也都考过，我们来看下。
问题描述
难度：中等
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回已排序的链表 。
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
输入：head = [1,1,1,2,3]
输出：[2,3]
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列
问题分析
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);
}
}
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);
}
}
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);
}
}
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)
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);
}
};