# remove duplicates from sorted list I&II

## remove duplicates from sorted list I&II

### I easy problem

Go throhgh the whole list.Use two pointers,`p`

point to head at first, `q`

point to next of `p`

. If `p`

and `q`

have different value, `p`

and `q`

move to their next. Otherwise, delete `q`

and move `q`

to its next.

```
1 /**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode(int x) : val(x), next(NULL) {}
7 * };
8 */
9 class Solution {
10 public:
11 ListNode *deleteDuplicates(ListNode *head) {
12 if ( !head || !head->next ) {
13 return head;
14 }
15 ListNode* p = head;
16 ListNode* q = head->next;
17 while ( q ) {
18 if ( p->val != q->val ) {
19 p = q;
20 q = p->next;
21 } else {
22 p->next = q->next;
23 delete(q);
24 q = p->next;
25 }
26 }
27 return head;
28 }
29 };
```

### II is not very head

When we solve the linked list problem, add a node before the head is always convience way to avoid the special condition of the head. We add a node before the head, and use three pointer `pre`

`p`

`q`

. if `p`

and `q`

have the same value, delete `q`

and make a mark. Otherwise check the mark, if marked delete `p`

.

```
1 /**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 * int val;
5 * ListNode *next;
6 * ListNode(int x) : val(x), next(NULL) {}
7 * };
8 */
9 class Solution {
10 public:
11 ListNode *deleteDuplicates(ListNode *head) {
12 if ( !head || !head->next ) {
13 return head;
14 }
15 ListNode* newHead = new ListNode(-1);
16 newHead->next = head;
17 ListNode* pre = newHead;
18 ListNode* p = head;
19 ListNode* q = head->next;
20 int mark = 0;
21 while ( q ) {
22 if ( p->val == q->val ) {
23 p->next = q->next;
24 delete(q);
25 q = p->next;
26 mark = 1;
27 } else {
28 if ( 1 == mark ) {
29 mark = 0;
30 delete(p);
31 pre->next = q;
32 p = q;
33 q = q->next;
34 } else {
35 pre = p;
36 p = p->next;
37 q = q->next;
38 }
39 }
40 }
41 if ( 1 == mark ) {
42 pre->next = q;
43 delete(p);
44 }
45 head = newHead->next;
46 delete(newHead);
47 return head;
48 }
49 };
```