BM16 删除有序链表中重复的元素-II

1 题目介绍

解法一:

建立哨兵节点然后遍历链表将唯一节点连接到哨兵节点上
时间复杂度：O(n)，其中n为链表节点数，只有一次遍历
空间复杂度：O(1)，只开辟了临时指针，常数级空间

public class Solution {
    
    /** * * @param head ListNode类 * @return ListNode类 */
    public ListNode deleteDuplicates (ListNode head) {
    
        // write code here
        if(head == null){
    
            return null;
        }
        // 1: 定义两个指针,一个用来找只出现一次的元素,一个用来连接该元素
        ListNode ret = new ListNode(1);
        ListNode tep = ret;
        ListNode cur = ret;
        cur.next = head;
        cur = cur.next;
        while(cur != null && cur.next != null){
    
            // 若不相等说明cur指向的就是唯一元素
            if(cur.val != cur.next.val){
    
                tep.next = cur;
                tep = tep.next;
                cur = cur.next;
            }else{
    
                // 若相等则继续往前走直达找到不相等的元素位置
                while(cur != null && cur.next != null && cur.val == cur.next.val){
    
                    cur = cur.next;
                }
                // 将cur指针指向下一个元素,若cur为空了说明后面的元素都找完了,此时需手动将空指针连接上去,否则就会跳出循环
                cur = cur.next;
                if(cur == null){
    
                    tep.next = null;
                }
            }
        }
        // 若遍历完cur位于最后一个元素,那么就需要手动将最后一个元素也连接上,因为是升序排列,能走到这里说明最后一个元素一定是唯一的
        if(cur != null && cur.next == null){
    
            tep.next = cur;
        }
        return ret.next;
    }
}

解法二:

利用递归的思想解决
时间复杂度：O(n)
空间复杂度：O(1)

public class Solution {
    
    /** * * @param head ListNode类 * @return ListNode类 */
    public ListNode deleteDuplicates(ListNode head) {
    
        if(head == null){
    
            return null;
        }
        if(head.next != null && head.val == head.next.val){
    //发现有重复值
                while(head.next != null && head.val == head.next.val){
    
                    head = head.next;//删除
            }
            return deleteDuplicates(head.next);//把与删除的那个结点相同的结点也进行删除
        }
        head.next = deleteDuplicates(head.next);//当没有发现重复值的情况，就一直进行递归操作
        return head;
    }
}

解法三:

利用hashmap进行两次遍历,第一遍记录每个数出现的次数,第二遍新建哨兵节点连接唯一节点.
时间复杂度：O(n)
空间复杂度：O(n)
此方法适用于链表顺序是随机的情况下

public class Solution {
    
    public ListNode deleteDuplicates (ListNode head) {
    
        //空链表
        if(head == null) 
            return null;
        HashMap<Integer,Integer> mp = new HashMap<>();
        ListNode cur = head;
        //遍历链表统计每个节点值出现的次数
        while(cur != null){
     
            if(mp.containsKey(cur.val))
                mp.put(cur.val, (int)mp.get(cur.val) + 1);
            else
                mp.put(cur.val,1);
            cur = cur.next;
        }
        ListNode res = new ListNode(0);
        //在链表前加一个表头
        res.next = head; 
        cur = res;
        //再次遍历链表
        while(cur.next != null){
    
            //如果节点值计数不为1 
            if(mp.get(cur.next.val) != 1) 
                //删去该节点
                cur.next = cur.next.next; 
            else
                cur = cur.next; 
        }
        //去掉表头
        return res.next; 
    }
}