每日一题《剑指offer》链表篇之删除链表中重复的结点

今日题目链接：删除链表中重复的结点

删除链表中重复的结点

难度：中等

描述

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

数据范围

数据范围：链表长度满足0≤n≤1000 ，链表中的值满足1≤val≤1000

进阶：空间复杂度 O(n) ，时间复杂度 O(n)

举例

例如输入{1,2,3,3,4,4,5}时，对应的输出为{1,2,5}，对应的输入输出链表如下图所示：

解题思路

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

代码语言：javascript复制

//遇到相邻两个节点值相同
if(cur.next.val == cur.next.next.val){ 
    int temp = cur.next.val;
    //将所有相同的都跳过
    while (cur.next != null && cur.next.val == temp) 
        cur.next = cur.next.next;
}

具体做法：

step 1：给链表前加上表头，方便可能的话删除第一个节点。

代码语言：javascript复制

ListNode res = new ListNode(0);
//在链表前加一个表头
res.next = pHead;

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

方法二:哈希表这道题幸运的是链表有序，我们可以直接与旁边的元素比较，然后删除重复。那我们扩展一点，万一遇到的链表无序呢？我们这里给出一种通用的解法，有序无序都可以使用，即利用哈希表来统计是否重复。

具体做法：

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

实现代码（java）

方法一:

代码语言：javascript复制

public class Solution {
    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 && cur.next.val == temp) 
                    cur.next = cur.next.next;
            }
            else 
                cur = cur.next;
        }
        //返回时去掉表头
        return res.next; 
    }
}

方法二:

代码语言：javascript复制

import java.util.*;
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        //空链表
        if(pHead == null) 
            return null;
        Map<Integer,Integer> mp = new HashMap<>();
        ListNode cur = pHead;
        //遍历链表统计每个节点值出现的次数
        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 = pHead; 
        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; 
    }
}

null 遍历链表数据统计

0 人点赞