83. 删除排序链表中的重复元素

题目描述

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。
返回 已排序的链表 。

方法1 双指针方式

描述

指针p去找寻是否为相同的节点
如果不是，则在cur后边进行添加，防止重复出现
如果是，直接跳过，遍历下一个节点

存在问题：不需要创建Set对象来存储重复值，因为链表经过排序，
        可以使用 cur.val 和 cur.next.val 相等时说明需要去重

代码

package easy.删除排序链表中的重复元素83;


import java.util.HashSet;
import java.util.Set;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        Set<Integer> set = new HashSet<>();
        ListNode p = head.next;
        ListNode cur = head;
        set.add(head.val);
        while(p != null) {
            if (set.contains(p.val)) {
                p = p.next;
            } else {
                set.add(p.val);
                cur.next = new ListNode(p.val);
                cur = cur.next;
                p = p.next;
            }
            cur.next = null;
        }
        return head;
    }
}

方法2

描述

指定 cur 指针指向头部 head
当 cur.next 的存在为循环结束条件，当二者有一个不存在时说明链表没有去重复的必要了
当 cur.val 和 cur.next.val 相等时说明需要去重，则将 cur 的下一个指针指向下一个的下一个，这样就能达到去重复的效果
如果不相等则 cur 移动到下一个位置继续循环

代码

package easy.删除排序链表中的重复元素83;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Solution2 {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return null;
        ListNode cur = head;
        while(cur.next != null) {
            if (cur.val == cur.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
}