▶ 删除单链表中的重复元素。
▶ 83. 把重复元素删得只剩一个，如 1 → 1 → 2 → 3 → 3 → 3 → 4 → 5 → 5 变成 1 → 2 → 3 → 4 → 5。注意要点：第一个元素就可能重复，最后一个元素可能是重复，多个连续重复。
● 自己的代码，18 ms，记录了发生重复的第一个元素的位置，使其指向下一个不同的元素的位置。
class Solution
{
public:
ListNode* deleteDuplicates(ListNode* head)
{
if (head == nullptr || head->next == nullptr)
return head; ListNode *output, *i, *j, *k;
for (i = head, j = head->next; i != nullptr; i = j)
{
for (; j != nullptr && i->val == j->val; j = j->next);
i->next = j;
}
return head;
}
};
● 大佬的代码，11 ms，逐格比较相邻两个结点，值相同则跨过后一结点。
class Solution
{
public:
ListNode* deleteDuplicates(ListNode* head)
{
for (ListNode* cur = head; cur && cur->next;)
{
if (cur->val == cur->next->val)
cur->next = cur->next->next;
else
cur = cur->next;
}
return head;
}
};
▶ 82. 把发生重复的元素删除得一个不剩。如 1 → 1 → 2 → 3 → 3 → 3 → 4 → 5 → 5 变成 2 → 4 。
● 自己的非递归版代码，8 ms
class Solution
{
public:
ListNode* deleteDuplicates(ListNode* head)
{
if (head == nullptr || head->next == nullptr)
return head;
for (; head != nullptr && head->next != nullptr && head->val == head->next->val;)// 去掉开头的重复结点
{
for (; head->next != nullptr && head->val == head->next->val; head = head->next);
head = head->next;
}
if (head == nullptr)
return head;
for (ListNode *prev = head, *cur = head->next; cur != nullptr && cur->next != nullptr; cur = prev->next)
{
if (cur->val == cur->next->val)
{
for (; cur->next != nullptr && cur->val == cur->next->val; cur->next = cur->next->next);
prev->next = cur->next;
}
else
prev = prev->next;
}
return head;
}
};
● 大佬的递归版代码，9 ms
class Solution
{
public:
ListNode* deleteDuplicates(ListNode* head)
{
if (head == nullptr || head->next == nullptr)
return head; int val = head->val;
ListNode *p = head->next;
if (p->val != val)
{
head->next = deleteDuplicates(p);
return head;
}
else
{
for (; p && p->val == val; p = p->next);
return deleteDuplicates(p);
}
}
};