有序链表删除重复节点

问题1

删除排序链表中重复元素，例如l1 为 1->2->2->3->3->4,删除之后为，1->2->3->4,简单来说就是重复元素保留一个。

原理

• 因为需要找重复元素，所以需要两层循环。第一层遍历整个链表，第二层找第一层的下一个节点不等于当前节点为止。
• 需要注意的是把第一层的节点dump出来，在第二层找完之后执行cur.next = next, 并且第一层循环继续循环。

代码

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

注意事项

• 需要dump出第一层的节点。

问题2

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。例如l1 为 1->2->2->3->3->4,删除之后为，1->4,简单来说就是重复元素都不保留。

原理

• 因为重复的元素都不保留，因此需要注意的是怎么判断一个元素是不是重复元素呢？这里可以联想到使用hashmap的数据结构存储。
• 因此就有判断当前元素在hashmap里面的元素个数，如果个数大于1 不放入链表。

代码

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null){
            return head;
        }
        Map<Integer,Integer> map = new HashMap<>();
        ListNode l1 = head;
        while(l1!=null){
            if(map.get(l1.val)!=null){
                map.put(l1.val,map.get(l1.val)+1);
            }else{
                 map.put(l1.val,1);
            }
            l1 = l1.next;
        }
        ListNode newHead = new ListNode(-1);
        ListNode run = newHead;
        while(head!=null){
            if(map.get(head.val)==1){
                run.next = head;
                run = run.next;
            }
            head = head.next;
        }
        run.next = null;
        return newHead.next;
    }
}

注意事项

• 上面两个问题都可以考虑采用递归的实现方案，比较简单。