JZ76 删除链表中重复的结点

题目

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 
例如，链表 1->2->3->3->4->4->5  处理后为 1->2->5

方法1 哈希表进行删除

思路

算法实现

LinkedHashMap实现顺序插入，不过查询速度会比较慢

具体做法：
    step 1：用哈希表统计每个字符的次数。
    step 2：在put前进行判断，如果有值则在原有的值进行+1，没有则默认值+1。
    step 3：对map进行遍历，对计数为1的值进行创建ListNode对象，然后拼接成一个链表。

代码

package mid.JZ76删除链表中重复的结点;

import java.util.LinkedHashMap;

class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
public class Solution {
    /**
     * 运行时间     62ms
     * 占用内存     11416KB
     * @param pHead
     * @return
     */
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null) {
            return null;
        }
        LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
        while(pHead != null) {
            map.put(pHead.val, map.getOrDefault(pHead.val, 0) + 1);
            pHead = pHead.next;
        }
        ListNode head = new ListNode(-1);
        ListNode p = head;
        for (Integer o : map.keySet()) {
            if (map.get(o) == 1) {
                p.next = new ListNode(o);
                p = p.next;
            }
        }
        p.next = null;
        return head.next;
    }


}

方法2 直接比较删除

思路

算法实现

这是一个升序链表，重复的节点都连在一起，我们就可以很轻易地比较到重复的节点，
然后将所有的连续相同的节点都跳过，连接不相同的第一个节点

具体做法：
    step 1：给链表前加上表头，方便可能的话删除第一个节点。
            ListNode res = new ListNode(0);
            //在链表前加一个表头
            res.next = pHead;                
    step 2：遍历链表，每次比较相邻两个节点，如果遇到了两个相邻节点相同，则新开内循环将这一段所有的相同都遍历过去。
    step 3：在step 2中这一连串相同的节点前的节点直接连上后续第一个不相同值的节点。
    step 4：返回时去掉添加的表头。

代码

package mid.JZ75字符流中第一个不重复的字符;

import java.util.HashMap;
import java.util.Map;

public class Solution2 {
    StringBuilder sb = new StringBuilder();
    Map<Character,Integer> map = new HashMap<>();

    //Insert one char from stringstream
    public void Insert(char ch) {
        sb.append(ch);
        map.put(ch, map.getOrDefault(ch, 0) + 1);
    }

    //return the first appearence once char in current stringstream

    /**
     * 运行时间     13ms
     * 占用内存     9952KB
     * @return
     */
    public char FirstAppearingOnce() {
        for (int i = 0; i < sb.length(); i++) {
            if (map.get(sb.charAt(i)) == 1) {
                return sb.charAt(i);
            }
        }
        return '#';
    }
}

方法3 哈希表+字符串（推荐使用）

思路

算法实现

除了使用字符串记录字符流，还可以用队列记录字符流，每次插入的时候，只需要将第一次出现的字符加入到队列中，然后正常计数。
查找第一个不重复出现的字符的时候，从队首开始查询哈希表，
如果出现次数为1，则返回该字符，如果不为1，则从队首将其弹出。

具体做法：
    step 1：准备一个队列来记录输入的字符流，用哈希表统计每个字符的次数，二者都是全局变量。
    step 2：在Insert函数中对输入的字符，加到队列最后，然后统计出现次数。
    step 3：在FirstAppearingOnce函数中，不断检查队首元素直到队列为空，队首出现次数为1次，就返回，
    队首出现次数不为1就弹出。，则返回#。

代码

package mid.JZ76删除链表中重复的结点;

public class Solution2 {
    /**
     *
     运行时间   54ms
     占用内存   11256KB
     * @param pHead
     * @return
     */
    public ListNode deleteDuplication(ListNode pHead) {
        if (pHead == null) return null;

        ListNode res = new ListNode(0);
        res.next = pHead;
        ListNode cur = res;
        while(cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int temp = cur.next.val;
                while(cur.next != null && temp == cur.next.val) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }
        return res.next;
    }
}