算法
(线性扫描) O(n)
为了方便处理边界情况，我们定义一个虚拟元素 dummy 指向链表头节点。
然后从前往后扫描整个链表，每次扫描元素相同的一段，如果这段中的元素个数多于1个，则将整段元素直接删除。
时间复杂度
整个链表只扫描一遍，所以时间复杂度是 O(n)。
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplication(ListNode* head) {
auto dummy = new ListNode(-1);
dummy->next = head;
auto p = dummy;
while (p->next) {
auto q = p->next;
while (q && p->next->val == q->val) q = q->next;
if (p->next->next == q) p = p->next;
else p->next = q;
}
return dummy->next;
}
};
家人们，最后这个p->next->next == q看好久了没看懂呜呜呜
代表没有重复的数
同感
q只移动一位的话 p->next->next == q 就成立。原因是一开始q = p->next，q只移动一位的话就变成了
q = p->next->next。
q只移动一位的话 p->next->next == q 就成立。原因是一开始q = p->next，q只移动一位的话就变成了
q = p->next->next。
现在明白了，感谢回复hh
懂了懂了，谢谢讲解qwq
滚蛋 这怎么代表没有重复的数呢
为啥不是啊求解释呜呜呜，看了好久
写成if (q->next == q) p = p->next; 这样好理解很多
q至少前进两位，当q只前进两位的时候，说明q经历的这两个点值不相同，所以p就往后移一位，当q移动两位以上时，说明这q经历的这些节点的值都相同，要将他们删除，同时p->next->next == q这个条件就不成立了，对应else语句中的p->next = q，p节点的next直接指向q节点，将中间的点删除
因为一开始q = p->next ，while语句里p->next->val == q->val一定成立一次，q就一定会向后移动一位。这时候若没有重复元素，q就在p->next->next这个节点上了。
为啥q一定会移动啊
while (q && p->next->val == q->val)里面 一开始我们初始化 q = p->next 所以q->val = p->next->val 所以while循环至少会运行一次
没有重复的数字的时候，q指针只走一步，对应p->next->next == q，确实是对应没有重复数字的情况😹
q指向了下一个与p-＞next不同的值，如果这个值是p-＞next-＞next的话p指针后移，如果不是，就指向q指针的地址（即下一个不一样的值）
这个我得理解是p,q之间只有一个数，而没有重复的数
auto q = p->next;
while (q && p->next->val == q->val) q = q->next;
这里q = p -> next 那q ->val 不是永远等于 p -> next -> val 吗
q是从p->next开始，把所有和p->next的值相等的一段都循环找出来。不考虑内存泄漏吗
需要delete dummy是吗？
一次内存泄露危害可以忽略
为什么这句话(q && p->next->val == q->val)写成( p->next->val == q->val&&q)就报seg错误？？
q如果是空节点，那么调用q->val就会段错误。这里还会有顺序问题啊，我以为同时判断呢
对滴，条件表达式从左到右依次执行。
//Java 实现
/*
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
/
class Solution {
public ListNode deleteDuplication(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode p = dummy;
while(p.next != null){ ListNode q = p.next; while(q!=null && p.next.val==q.val) q=q.next; if(p.next.next==q) p=p.next; else p.next=q; } return dummy.next; }}
struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; class Solution { public: ListNode* deleteDuplication(ListNode* head) { // 基本情况：如果当前链表为空或只有一个节点，没有重复，直接返回。 if (head == NULL || head->next == NULL) return head; // 如果当前节点的值与下一个节点的值相同 if (head->val == head->next->val) { // 跳过所有重复的节点 ListNode* move = head->next; while (move != NULL && head->val == move->val) { move = move->next; } // 从第一个不重复的节点开始递归 return deleteDuplication(move); } else { // 如果当前节点的值与下一个节点的值不同，保留当前节点 // 并递归处理其余的链表 head->next = deleteDuplication(head->next); return head; } } };能不能来个大佬说说为什么要建立一个dummy指向头节点呀，还有这里的头结点有没有储存数据呀，我有点懵逼了，上面的操作似乎也没有删除头结点呀，跪求有个小回复
auto dummy = new ListNode （-1）这一句是建立一个值为-1，next指向空的节点，然后让这个节点作为虚拟节点插在原来头节点前面，目的是为了应对可能删除头节点的情况，而单链表只能找下一个节点，所以虚拟头节点就是为了能方便找到并删除头节点。另外，最后返回的是虚拟头节点的next节点作为头节点的链表，所以并不用真的删掉虚拟头节点
那大佬我想问一下，最后return 的是dummy的next，为什么不直接输出head呢，就算第一个被删了head也会返回一个空啊，比如4,4,4我用dummy的next没问题，但是用head返回就不行
在这段代码中，return dummy->next; 返回的是修改后的链表的头节点。这个头节点是虚拟头节点dummy的next指针所指向的节点。
由于链表的头节点head在处理过程中可能被修改（例如，如果头节点是重复的，它会被删除），
所以返回dummy->next可以确保无论原始头节点是否被删除，都能正确返回新链表的开始位置。
在执行deleteDuplication函数时，链表中的重复元素会被删除，而唯一的元素会被保留。
由于虚拟头节点dummy始终存在，并且其next指针在链表的开始位置，所以dummy->next始终
指向链表的第一个有效元素。这样，即使原始链表的头节点被删除，返回的链表仍然从第一
个非重复的元素开始。
牛逼
class Solution {
public:
ListNode deleteDuplication(ListNode head) {
if(head==NULL)
return NULL;
ListNode *p=head,*q; bool judge; int n; while(p->next!=NULL) { judge=0; for(q=p->next;q!=NULL;) if(q->val==p->val) { judge=1; if(q->next!=NULL) q->val=q->next->val,q->next=q->next->next; else { n=q->val; q=p; while(q->next->val!=n) q=q->next; q->next=NULL; q=NULL; } } else q=q->next; if(judge) if(p->next!=NULL) p->val=p->next->val,p->next=p->next->next; else { if(p->val==head->val) return NULL; n=p->val; p=head; while(p->next->val!=n) p=p->next; p->next=NULL; } else p=p->next; } return head; }};
if (p->next && p->next->next == q) p = p->next;
这一步判断p->next好像没有什么用处?
对滴，这里
p->next一定是存在的，所以可以去掉hh为什么我去掉后，提示Segmentation Fault啊
上面的代码已经是去掉之后的样子，是可以Accept的，你可以参考一下。
这个题老大似乎没有考虑四释放内存的呢？
是的，这里偷了个懒hh 面试的时候最好把内存释放掉
while (q && p->next->val == q->val) q = q->next;感觉这里每次第一步没必要算
while (q && p->next->val == q->val) q = q->next;感觉这里每次第一步没必要算
## 可以看看我写的图解
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode deleteDuplication(ListNode head) { if (head == null || head.next == null) return head; ListNode ans = new ListNode(-1), p; ans.next = head; p = ans; while (p.next != null) { ListNode x = p.next; while (x != null && x.val == p.next.val) x = x.next; if (p.next.next == x) p = p.next; else p.next = x; } return ans.next; } } /* ans: 答案，即删除后的链表头 p : 正确的节点。p走过的路径即是删除后的路径 ne : p的前面，用作探子，检验正确与否 x : 用于寻找ne前面的第一个与ne不相等元素 代码流程： 找到ne前面第一个与ne不相等的元素 若就是下一个元素： 说明正确，让p走过 若不是下一个元素： 说明不正确，让ne过去再探 例子： [1 2 3 3 4 4 5] ans(p)->ne // 初始化 ans(p)->ne->x // 找到ne前面第一个与ne不相等的元素 ans ->p ->ne // 就是下一个：让p走到ne，作为正确答案 ans ->p ->ne->x // 找到ne前面第一个与ne不相等的元素 ans -> ->p ->ne // 就是下一个：让p走到ne，作为正确答案 ans -> ->p ->ne ->x // 找到ne前面第一个与ne不相等的元素 ans -> ->p ->ne // 不是下一个：让ne过去再探 ans -> ->p ->ne ->x // 找到ne前面第一个与ne不相等的元素 ans -> ->p ->ne // 不是下一个：让ne过去再探 ans -> ->p ->ne->x // 找到ne前面第一个与ne不相等的元素 ans -> -> ->p ->ne // 就是下一个：让p走到ne，作为正确答案 得到ans： ans ->1 ->2 ->5 // p把正确答案连接了起来，得到ans return ans.next */为什么auto p = dummy而不是p = head呢，我写成= head在处理空链表时有错
y总怎么又没有释放空间（狗头）
while (p->next) {
auto q = p->next;
while (q && p->next->val == q->val) q = q->next;
这段中p->next不是以及不为空了吗，那q不是也不为空，为什么还要在第二个while循环中判断q是否为空，不加就会SF？
class Solution { public: ListNode* deleteDuplication(ListNode* head) { int arr[101];//哈希法 memset(arr , 0 , sizeof(arr)); ListNode* p = head; while(p) arr[p->val] ++ , p = p->next; ListNode* h = new ListNode(0); p = h; for(int i = 0 ;i <= 100 ;i ++) if(arr[i] == 1) p->next = new ListNode(i) , p = p->next; return h->next; } };链表加头的方法学到了，没想到还可以这样规避掉表头前指针的特殊处理。每次写这种题的时候总要考虑表中元素个数为0、1、2的特殊情况，加上个头可以少些很多啰嗦的代码。
为什么把 return dummy->next; 换成 return head; 就报错了？
最后返回的时候为什么p->next不行，为什么一定要dummy->next呢？