剑指offer—删除(排序)链表中重复元素 解答

剑指offer—删除(排序)链表中重复元素

1.排序链表—leetcode82

题目描述

给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。

思路—快慢双指针指针

首先我们注意到链表是顺序的,说明相等的元素都是集合在一起的,我们可以利用这一特点,判断前后节点元素是否相等

我们可以使用两个指针,一个在前fast一个在后slow(相差一个位置),前面的指针负责侦查相同的元素,如果有相同的元素那么前面的指针就跳过他们,跳过后告诉后面的指针“你连接到我这个位置来,我帮你清空了前面相等的元素”,没有的话就两个指针一同往前走一步,知道走到链表尽头

  • 但是有一种情况需要有一点特殊处理,就是第一个和第二个元素相等,此时头元素被删除了,我们不再使用头结点作为返回值,而是需要使用慢指针的下一个元素返回

问题:为什么慢指针要初始化为一个新指针,而不是让快指针指向第二个元素,第一个元素指向慢指针?

这个问题很容易回答,首先如果你直接初始化第二个元素为快指针指向,那么快指针就无法侦查第一个元素和第二个元素是否相等;其次返回时如果头结点被删除了,那你返回的值就是无法确定的

代码
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode fast = head,slow = new ListNode(0),h = slow;
        slow.next = head;
        while(fast!=null&&fast.next!=null){
            if(fast.val==fast.next.val){
                while(fast.next!=null&&fast.val==fast.next.val) fast = fast.next;
                slow.next = fast.next;
            }else slow = slow.next;
            fast = fast.next;
        }
        return h.next!=head?h.next:head;
    }
}

2.非排序链表

删除重复元素只留一个—leetcode83

题目描述

给定一个链表,删除所有重复的元素,使得每个元素只出现一次。

思路—哈希保存次数累加

因为无法排序就无法不使用辅助空间,我们可以使用哈希表保存每个节点数值出现的次数,每次连接时判断下一个元素是否出现过(也就是map中的出现次数大于等于1),如果出现过就直接跳过下一个元素,否则就继续迭代判断;考虑到头结点可能被删除,所以我们需要一个哨兵节点作为头结点

为了能跳过重复的元素,我们就不能使用当前元素去判断,要使用下一个元素去判断,因为在链表中你是无法删除当前节点的,你只能去连接下一个节点

代码
class Solution {
    public ListNode deleteDuplicates(ListNode pHead) {
        Map<Integer,Integer> map = new HashMap<>();
        ListNode node = new ListNode(0);node.next = pHead;
        while(node.next!=null){
            int val = node.next.val;
            if(map.get(val)==null){
                map.put(val,1);
                node = node.next;
            }
            else node.next = node.next.next;
        }
        return pHead;
    }
}

删除重复元素的所有

题目描述

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

示例 1:

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

输入: 1->1->1->2->3
输出: 2->3
思路—哈希保存次数累加,多一次循环

我们通过上一题可以删除重复元素中的N-1个元素,而无法全部删除,因为一次遍历你无法删除出现过多次的每一个元素,所以我们需要在进行一次循环,把map中出现次数大于1的给删除,考虑到头结点可能被删除,所以我们需要一个哨兵节点作为头结点

代码
class Solution {
    public ListNode deleteDuplicates(ListNode pHead) {
        if(pHead==null) return null;
        ListNode node = null;
        Map<Integer,Integer> map = new HashMap<>();
        node = new ListNode(0);node.next = pHead;
        while(node.next!=null){
            int val = node.next.val;
            if(map.get(val)==null){
                map.put(val,1);
                node = node.next;
            }
            else{
                map.put(val,map.get(val)+1);
                node.next = node.next.next;
            }
        }
        node = new ListNode(0);node.next = pHead;
        final ListNode head = node;
        while(node.next!=null){
            int val = node.next.val;
            if(map.get(val)>1){
                node.next = node.next.next;
            }else{
                node = node.next;
            }
        }
        return head.next;
    }
}