2021/3/25 删除有序链表中的重复元素

题目描述

描述转载自《83. 删除排序链表中的重复元素》
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例1

输入: 1->1->2
输出: 1->2

示例2

输入: 1->1->2->3->3
输出: 1->2->3

解题思路

1. 因为有可能头结点会被删除，所以定义一个哑结点 dummy，连接头节点的前面；
2. 因为是有序链表，所以重复元素只会相邻；
3. 定义 cur 指针指向 dummy，如果 cur.next 与 cur.next.next 值相同，说明它们两个重复了，删除 cur.next 节点，也就是 cur.next = cur.next.next；
4. 如果 cur.next 与 cur.next.next 值不同，那就说明当前 cur.next 的值没有重复元素，cur = cur.next。

Java代码实现

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode dummy = new ListNode(Integer.MAX_VALUE);
        dummy.next = head;
        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return dummy.next;
    }
}