1 问题
????????存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
????????返回同样按升序排列的结果链表。
1.1 示例
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
1.2 示例
输入：head = [1,1,1,2,3,3]
输出：[2,3]
2 思路
2.1 遍历
?图1 遍历
?2.2 递归
图2 递归
3 编程
3.1 遍历
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
// 空链表和只有一个节点的链表
if (!head || !head->next)
return head;
ListNode* dummy = new ListNode(0, head); // 哑节点
ListNode* prev = dummy; // 先前节点
while (head)
{
// 找到最后一个重复数字
while (head->next && head->val == head->next->val)
{
head = head->next;
}
// 没有重复节点
if (prev->next == head)
{
prev = head;
}
else
{
prev->next = head->next;
}
head = head->next;
}
return dummy->next;
}
};
3.2 递归
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head)
{
if (!head || !head->next)
{
return head;
}
if (head->val != head->next->val)
{
head->next = deleteDuplicates(head->next);
}
else
{
ListNode* next = head->next;
while(next && head->val == next->val)
{
next = next->next;
}
return deleteDuplicates(next);
}
return head;
}
};