18.2 删除链表中重复的结点

Leetcode

题目描述

在一个排序的链表中，重复出现的结点全部删除，一个都不保留。例如 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 处理后为 1 -> 2 -> 5。

解题思路

用递归处理，deleteDuplicates(head) 返回以 head 开头的链表去重后的头节点：

• head 与下一个节点的值相同：head 属于重复的一组，跳过与它值相同的所有节点，对后面第一个不同的节点递归，结果就是答案，head 本身不保留；
• head 与下一个节点的值不同：head 一定保留，对 head.next 递归，把结果接在 head 后面。

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