leetcode刷题82. 删除排序链表中的重复元素 II，Medium（Java）递归+迭代

1.题目描述2.解法

2.1 递归

2.1.1 思路2.1.2 Java代码 2.2 迭代

2.2.1 思路2.2.2 Java

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

示例 1：

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

示例 2：

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

提示：

链表中节点数目在范围 [0, 300] 内-100 <= Node.val <= 100题目数据保证链表已经按升序 排列 2.解法

tips：链表看不懂可以画图。

递归的三要素

明确函数的功能递归的结束条件函数的等价关系

1.函数的功能是删除重复节点
2.递归的结束条件为到了链表的最后节点
3.函数的等价关系head.next = self.deleteDuplicates(head.next)

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 cur = head.next;
            while(cur!=null&&head.val == cur.val){
                cur = cur.next;
            }
            return deleteDuplicates(cur);
        }
        return head;
    }
}

时间复杂度 O(n^2)
首先因为需要返回链表头，所以新建一个节点称为dummy（哑节点）保存头节点，用于返回。
之后因为需要删光所有的重复节点，所以需要首先保存重复节点前的节点cur。
先保存这个重复节点的值，通过cur.next和值比较相同就删除。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(0,head);
        ListNode cur = dummy;
        while(cur.next!=null&&cur.next.next!=null){
            if(cur.next.val ==cur.next.next.val){
                int value = cur.next.val;
                while(cur.next!=null&&cur.next.val==value){
                    cur.next = cur.next.next;
                }
            }
            else{
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}