leetcode删除排序链表中的重复元素 II(java递归和非递归)

落日映苍穹つ 2021-09-28 08:52 265阅读 0赞

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 *没有重复出现 *的数字。

**示例 1:**

输入: 1->2->3->3->4->4->5
    输出: 1->2->5

**示例 2:**

输入: 1->1->1->2->3
    输出: 2->3

非递归自己做的发现很差虽然过了

public ListNode deleteDuplicates(ListNode head) {
            if(head==null||head.next==null){
                return head;
            }
            ListNode node = new ListNode(0);
            node.next = head;
            List<Integer> list = new ArrayList<>();
            List<Integer> rrmove=new ArrayList<>();
            while (true) {
                node = node.next;
                Integer i = node.val;
                if (list.contains(i)) {
                    if(!rrmove.contains(i)){
                        rrmove.add(i);
                    }
                } else {
                    list.add(i);
                }
                if (node.next == null) break;
            }
            for (int i = 0; i <rrmove.size() ; i++) {
                list.remove(rrmove.get(i));
            }
            ListNode reshead = new ListNode(0);
            ListNode heads = new ListNode(0);
            reshead.next=heads;
            for (int i = 0; i < list.size(); i++) {
                ListNode res = new ListNode(list.get(i));
                heads.next = res;
                heads = heads.next;
            }
            return reshead.next.next;
        }

看评论大佬们写的

public ListNode deleteDuplicates(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            //判断是否是相等的值与下一个
            if (head.val == head.next.val) {
                ListNode next = head.next;
                //如果重复的值就向下循环找到不重复的那个值然后继续深搜进行向下判断返回使其能相连接
                do {
                    next = next.next;
                } while (next != null && next.val == head.val);
                return deleteDuplicates(next);
            } else {
                //不重复就名当前的head连接下一个返回并继续深搜
                head.next = deleteDuplicates(head.next);
                return head;
            }
        }