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

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 347 阅读时长 ≈ 1 分钟

考点

  • 双指针

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
	public:
		ListNode* deleteDuplicates(ListNode* head) {
			if (head == nullptr) return nullptr;
			ListNode *dummyNode = new ListNode(-1), *curNew = dummyNode;
			ListNode *left = head, *right = head->next;
			while (left != nullptr) {
				right = left->next;
				while (right != nullptr && left->val == right->val)	right = right->next;
				if (left->next == right) {
					curNew->next = left;
					left = left->next;
					curNew = curNew->next;
				} else left = right;
			}
			curNew->next = nullptr;
			return dummyNode->next;
		}
};

思路

本题是83. 删除排序链表中的重复元素的升级版，思路一样，也是使用双指针；左指针指向需要留下的元素，右指针作为游标指针

分为两种情况

  1. 左指针指向的值和右指针指向的值不同，说明左指针需要被留下，插入新链表
  2. 左指针指向的值和右指针指向的值相同，说明左右指针指向的值都需要被删除；待右指针指向第一个不同值的节点时，将左指针更新为该节点，开启新一轮判定

本题实际上每次比较的是两个相邻节点，所以左右指针其实可以用一个游标指针来代替，即head和head->next

改写后代码如下，逻辑与效果是一样的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
	public:
		ListNode* deleteDuplicates(ListNode* head) {
			ListNode *dummyHead = new ListNode(-1, head), *curNew = dummyHead;
			while (head != nullptr) {
				if (head->next == nullptr || head->val != head->next->val) {
					curNew->next = head;
					curNew = curNew->next;
				}
				while (head != nullptr && head->next != nullptr && head->val == head->next->val) {
					head = head->next;
				}
				head = head->next;
			}
			curNew->next = nullptr;
			return dummyHead->next;
		}
};