题解 | #删除链表中重复的结点#

删除链表中重复的结点

http://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef

思路

*链表有序，则要删除重复节点首先要注意的有三点

一如果重复元素出现在链表头部，要使用哨兵插入链表头部进行化简，降低操作链表的难度
二如果要删除的节点在尾部，直接对尾部节点赋值null （这只考虑到删除一个节点的情况）。当重复元素出现在尾部时，直接把尾部首先出现重复的节点赋值为null即可。
三头部尾部处理完，则出现重复节点的位置只能在链表中间，只需把前驱节点指向下下个指针head.next = head.next.next(这只考虑到有两个重复元素而已，当出现三个重复元素，则需要重考虑)

以上是只有两个重复节点情况，当重复节点大于3时，还要考虑使用额外的数组来存储删除的节点，把重复的节点按照存储需要删除的节点进行一一删除。

解法一使用额外数组存储要删除的元素

复杂度分析：时间复杂度：O(n)，其中n为遍历一次链表空间复杂度：O(n)，创建一个存储删除节点的数组

用额外数组进行删除会临时占用n个空间，优化方案是直接删除法

解法二官方直接删除法

step 1：给链表前加上哨兵，方便删除第一个节点。
step 2：遍历链表，每次比较相邻两个节点，如果遇到了两个相邻节点相同，则新开内循环将这一段所有的相同都遍历过去。
step 3：在step 2中这一连串相同的节点前的节点直接连上后续第一个不相同值的节点。
step 4：返回时去掉添加的表头。

复杂度分析：时间复杂度：O(n)，其中n为链表节点数，只有一次遍历空间复杂度：O(1)，只开辟了临时指针，常数级空间

解法三哈希表有序无序都可用

step 1：遍历一次链表用哈希表记录每个节点值出现的次数。
step 2：在链表前加一个哨兵，方便删除表头元素。
step 3：再次遍历该链表，对于每个节点值检查哈希表中的计数，只留下计数为1的，其他情况都删除。
step 4：返回时去掉增加的表头。

复杂度分析：时间复杂度：O(n)，其中n为链表节点数，只有一次遍历空间复杂度：O(n)，创建一个数值计数的哈希表

//解法一 使用额外数组存储要删除的元素
    //如果链表为空或只有一个节点则直接返回头节点
    if (!pHead || !pHead.next) {
        return pHead;
    }
    //创建一个需要存储删除的节点
    const delnode = [];
    //加入哨兵
    let phead = new ListNode(-1);
    phead.next = pHead;
    let del = phead;
    let head = phead;
    //保留循环前一个节点
    let pre;
    //头节点有哨兵在，只需处理中部和底部节点
    //向使用数组存取要删除的节点
    while(head.next) {
        if (head.val === head.next.val){
            delnode.push(head);
        //回环判断前节点
        } else if(pre && head.val === pre.val){
            delnode.push(head);
        }
        pre = head;
        head = head.next;
    }
//     解决中部n个重复问题
    while(delnode.length) {
        if(delnode[0].val === del.next.val) {
            del.next = del.next.next;
            delnode.shift();
            continue;
        }
        del = del.next; 
    }
    //接下来处理尾部出现重复的问题
    if(pre.val === pre.next.val) {
        del.next = null;
    }
    return phead.next;

//官方解法二 直接删除法
    let res = new ListNode(-1);
    res.next = pHead;
    let cur = res;
    while(cur.next && cur.next.next){
        if(cur.next.val === cur.next.next.val) {
            let temp = cur.next.val;
            while(cur.next && cur.next.val === temp){
                cur.next = cur.next.next;
            }
        } else {
            cur = cur.next;
        }
    }
    return res.next;

//解法三 适用于有序无序的哈希表法
    let cur = pHead;
    const map = new Map();
     //遍历链表，用哈希表查看有无重复数，并累加计数
    while(cur){
        if(map.has(cur.val)){
            map.set(cur.val, map.get(cur.val)+1)
        } else {
            map.set(cur.val,1);
        }
        cur = cur.next;
    }
    //创建哨兵
    let pre = new ListNode(-1);
    pre.next = pHead;
    cur = pre;
   //遍历链表 删除大于1的重复数
    while(cur.next){
        if(map.get(cur.next.val) !== 1) {
            cur.next = cur.next.next;
        } else {
            cur = cur.next;
        }
    }
    return pre.next