# ￼Remove Duplicates from Sorted List II

## Question

### Problem Statement

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

#### Example

Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

## 题解

ListNode *dummy = new ListNode(0);
ListNode *node = dummy;


1. 此题需要将值相等的节点全部删掉，而删除链表的操作与节点前后两个节点都有关系，故需要涉及三个链表节点。且删除单向链表节点时不能删除当前节点，只能改变当前节点的next指向的节点。
2. 在判断val是否相等时需先确定node->nextnode->next->next均不为空，否则不可对其进行取值。

### C++ - Wrong

/**
* Definition of ListNode
* class ListNode {
* public:
*     int val;
*     ListNode *next;
*     ListNode(int val) {
*         this->val = val;
*         this->next = NULL;
*     }
* }
*/
class Solution{
public:
/**
*/
return NULL;
}

ListNode *dummy;
ListNode *node = dummy;

while (node->next != NULL && node->next->next != NULL) {
if (node->next->val == node->next->next->val) {
int val = node->next->val;
while (node->next != NULL && val == node->next->val) {
ListNode *temp = node->next;
node->next = node->next->next;
delete temp;
}
} else {
node->next = node->next->next;
}
}

return dummy->next;
}
};


### 错因分析

1. 节点dummy的初始化有问题，对类的初始化应该使用new
2. 在else语句中node->next = node->next->next;改写了dummy-next中的内容，返回的dummy-next不再是队首元素，而是队尾元素。原因很微妙，应该使用node = node->next;，node代表节点指针变量，而node->next代表当前节点所指向的下一节点地址。具体分析可自行在纸上画图分析，可对指针和链表的理解又加深不少。

### Python

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
# @return {ListNode}
return None

dummy = ListNode(0)
node = dummy
while node.next is not None and node.next.next is not None:
if node.next.val == node.next.next.val:
val_prev = node.next.val
while node.next is not None and node.next.val == val_prev:
node.next = node.next.next
else:
node = node.next

return dummy.next


### C++

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
if (head == NULL) return NULL;

ListNode dummy(0);
ListNode *node = &dummy;
while (node->next != NULL && node->next->next != NULL) {
if (node->next->val == node->next->next->val) {
int val_prev = node->next->val;
// remove ListNode node->next
while (node->next != NULL && val_prev == node->next->val) {
ListNode *temp = node->next;
node->next = node->next->next;
delete temp;
}
} else {
node = node->next;
}
}

return dummy.next;
}
};


### Java

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
if (head == null) return null;

ListNode dummy = new ListNode(0);
ListNode node = dummy;
while(node.next != null && node.next.next != null) {
if (node.next.val == node.next.next.val) {
int val_prev = node.next.val;
while (node.next != null && node.next.val == val_prev) {
node.next = node.next.next;
}
} else {
node = node.next;
}
}

return dummy.next;
}
}


### 源码分析

1. 首先考虑异常情况，head 为 NULL 时返回 NULL
2. new一个dummy变量，dummy->next指向原链表头。(C++中最好不要使用 new 的方式生成 dummy, 否则会有内存泄露)
3. 使用新变量node并设置其为dummy头节点，遍历用。
4. 当前节点和下一节点val相同时先保存当前值，便于while循环终止条件判断和删除节点。注意这一段代码也比较精炼。
5. 最后返回dummy->next，即题目所要求的头节点。

Python 中也可不使用is not None判断，但是效率会低一点。