题解 | #删除有序链表中重复的元素-II#

问题描述

假设你有一串珠子，这些珠子按照从小到大的顺序排列。现在你要做的就是把那些重复的珠子拿掉，只留下出现过一次的珠子。

示例

• 输入：1 → 2 → 3 → 3 → 4 → 4 → 5
• 输出：1 → 2 → 5
• 输入：1 → 1 → 1 → 2 → 3
• 输出：2 → 3

解决方法

我们可以用一个简单的步骤来解决这个问题：

1. 从头开始：我们从第一个珠子开始看。
2. 比较相邻的珠子：每次我们看看当前珠子上的数字和它后面的珠子上的数字是不是一样的。
3. 跳过重复的珠子：如果发现重复的珠子，就跳过这些重复的珠子，直接连到下一个不同的珠子。
4. 继续往前走：如果当前珠子和后面的珠子不一样，就把手指（也就是我们用来看珠子的那个点）向前移动一格。
5. 一直做到最后：直到我们看到了最后一个珠子为止。

具体步骤

假设我们有一串珠子：1 → 2 → 3 → 3 → 4 → 4 → 5。

1. 从头开始：我们从第一个珠子 1 开始看。
2. 比较相邻的珠子：第一个珠子 1 和第二个珠子 2 不一样，所以我们把手指移到 2 上。
3. 继续比较：第二个珠子 2 和第三个珠子 3 不一样，所以我们把手指移到 3 上。
4. 比较相邻的珠子：第三个珠子 3 和第四个珠子 3 是一样的，所以我们跳过第四个珠子 3，直接连到第五个珠子 4。
5. 继续比较：第五个珠子 4 和第六个珠子 4 是一样的，所以我们跳过第六个珠子 4，直接连到第七个珠子 5。
6. 比较相邻的珠子：第七个珠子 5 和后面没有珠子了，所以我们停止。

最终结果

经过上述步骤之后，我们得到的结果就是：1 → 2 → 5。

代码实现

接下来，我们用简单的 Java 代码来实现这个过程：

import java.util.*;

class Solution {
    // 定义链表节点
    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    // 删除链表中的重复元素
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return null;
        }

        // 使用哑节点来简化边界情况处理
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode current = head;

        while (current != null) {
            // 寻找重复元素
            while (current.next != null && current.val == current.next.val) {
                current = current.next;
            }

            // 如果当前节点不是重复节点，则移动 prev
            if (prev.next == current) {
                prev = prev.next;
            } else {
                // 如果当前节点是重复节点，则跳过所有重复节点
                prev.next = current.next;
            }

            // 移动到下一个节点
            current = current.next;
        }

        return dummy.next;
    }
}

示例1

输入：{1, 2, 2}

• 原链表：1 → 2 → 2
• 处理后：1

示例2

输入：{1, 1, 1, 2, 3}

• 原链表：1 → 1 → 1 → 2 → 3
• 处理后：2 → 3

如果这篇文章对你有帮助，请点个免费的赞👍，让它帮助更多的人。