面试经典150题 P82 删除排序链表中的重复元素 II

---

时间轴

时间轴

2025-11-20

init

链表

---

题目：

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

https://leetcode.cn/problems/remove-duplicates-from-sorted-list-ii/description/?envType=study-plan-v2&envId=top-interview-150

注意题目要求删除原始链表中所有重复数字的节点，只留下不同的数字。

对于链表删除题目，创建一个虚拟头节点可以免去特殊情况判断。

class Solution {
    public:
	ListNode *deleteDuplicates(ListNode *head)
	{
		if (head == nullptr) {
			return head;
		}

		ListNode *virt_head = new ListNode;
		virt_head->next = head;

		ListNode *prev = virt_head, *curr, *duplicate;
		int i, val;

		while (prev->next != nullptr) {
			val = prev->next->val;
			curr = prev->next;
			for (i = 0; curr != nullptr; i++) {
				if (curr->val == val) {
					curr = curr->next;
				} else {
					break;
				}
			}
			if (i == 0) {
				break;
			} else if (i == 1) {
				prev = prev->next;
				continue;
			} else {
				while (prev->next != curr) {
					duplicate = prev->next;
					prev->next = duplicate->next;
					delete duplicate;
				}
			}
		}
		head = virt_head->next;
		delete virt_head;
		return head;
	}
};