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

示例 1:

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

示例 2:

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

看到这个题第一个想法就是使用hashmap统计节点数字出现的次数,当然这种方法一下就能想到却比较僵硬

解法如下:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(null==head||null==head.next){
            return head;
        }
        
        ListNode dhead = head;
        HashMap<Integer,Integer> map = new HashMap<>();
        while(dhead!=null){
            if(map.containsKey(dhead.val)){
                map.put(dhead.val,map.get(dhead.val)+1);
            }else{
                map.put(dhead.val,1);
            }
            dhead = dhead.next;
        }
        
        ListNode newNode = new ListNode(-1);
        ListNode hh = newNode;
        dhead = head;
        while(dhead!=null){
            if(map.get(dhead.val)==1){
                newNode.next = new ListNode(dhead.val);
                newNode = newNode.next;
            }
            dhead = dhead.next;
        }
        return hh.next;
    }
}

让我们换个稍微优雅点的解法做这个题吧.

我们可以用两个指针,一个pre,一个cur。
1.当cur与他的next值不相等时,让pre走到cur的位置(这是我们想要的节点),cur继续往下走。
2.当cur与他的next相等的时候,pre就不能走了,这个节点并不是我们想要的节点,我们让cur继续往下走直到与next值不相等时,此时我们依然不可以移动pre,因为这个节点也不能保证就是不重复的,所以我们让pre的next等于cur的next(即重复值节点的下一个节点,但是你此时也不知道这个节点是不是也重复),cur接着往下走。此时我们重复1.2.的步骤就可以得到想要的结果(不是重复值得节点pre就走,是重复值得就一直指向next)。

解法如下:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(null==head||null==head.next){
            return head;
        }
        
        ListNode dhead = new ListNode(-1);
        dhead.next = head;
        ListNode pre = dhead;
        ListNode cur = head;
        while(cur!=null&&cur.next!=null){
            if(cur.val!=cur.next.val){
                pre = cur;
                cur = cur.next;
            }else{
                while(cur.next!=null&&cur.val==cur.next.val){
                    cur = cur.next;
                }
                pre.next = cur.next;
                cur = cur.next;
            }
        }
        return dhead.next;
    }
}
Last modification:November 5th, 2019 at 04:19 am
大家一起分享知识,分享快乐