- Remove Duplicates from Sorted List II:题目链接
方法1：双指针
基本思想：用两个指针，一个快指针fast用来寻找重复元素的最后一个元素，漫指针fast用来链接重复元素之前的元素。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
// 时间复杂度O(N) 空间复杂度O(1) 双指针
struct ListNode* deleteDuplicates(struct ListNode* head) {
struct ListNode *dummy = (struct ListNode *) malloc(sizeof(struct ListNode));
dummy->next = head;
// fast : 用来找到重复元素中 的最后一个元素
// slow : 指向重复元素之前的元素
struct ListNode *fast = head, *slow = dummy;
while (fast) {
while (fast->next != NULL && fast->val == fast->next->val) {
fast = fast->next;
}
if (slow->next != fast) {
slow->next = fast->next;
fast = slow->next;
} else {
slow = slow->next;
fast = fast->next;
}
}
return dummy->next;
}
pS:源代码链接