---
# System prepended metadata

title: 82. 删除排序链表中的重复元素 II     【遞迴】【medium】

---

# 82. 删除排序链表中的重复元素 II     【遞迴】【medium】

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

 

示例 1：

![](https://i.imgur.com/j7hxAV1.png)

```
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
```
示例 2：

![](https://i.imgur.com/90MShs3.png)

```
输入：head = [1,1,1,2,3]
输出：[2,3]
```
 

提示：

链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列
通过次数226,770提交次数425,659

題解思路：

**遞迴終止條件，不需要再遞迴處理的狀case：**
1. head 為 null時，代表鏈表沒有任何節點，直接回傳head。
2. head.next為null時，代表鏈表只有一個頭節點，回傳head。

**遞迴調用**
1. 如果 `head.val != head.next.val`，當前head節點值不等於`head.next`節點值，則保留head節點，但`head.next`要不要保留還不知道，需對`head.next`遞迴處理。所以`head.next`作為頭節點，去重複節點，所以`head.next=deleteDuplicates(head.next);`
2. 如果head.val == head.next.val時，即為當前頭節點值等於下一個節點值，所以head節點需刪除，並且head之後與所有與head值相等的節點都需要刪除，刪到何時為止，需用move指針向後遍歷到找到與head.val不同時，此時move以前所有節點不保留，所以遞迴處理`deleteDuplicates(move)`

**返回結果**
1. 題目讓我們刪除了值重複的節點後剩餘的鏈表，結合上面兩種遞迴處理狀況：
* 如果`head.val != head.next.val` 頭節點需要保留，返回head
* 如果`head.val == head.next.val` 頭節點需要被刪除，返回`deleteDuplicate(move)`

```java=
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next==null) return head;

        if(head.val!=head.next.val){
            head.next =  deleteDuplicates(head.next);
        }else{
            ListNode move = head.next;
            while(move !=null && head.val == move.val){
                move = move.next;
            }
            return deleteDuplicates(move);
        }
        return head;
    }
}

```

