【数据结构与算法】之有序链表去重（不保留重复元素）

艾伦耶格尔

发布于 2025-08-28 15:27:19

1880

文章被收录于专栏：Java基础Java基础

1.问题描述

给定一个已排序的单链表的头节点 head，要求去除链表中所有重复的元素，重复元素一个不留，并返回新的头节点。

图一：

图二：

输入输出示例：

示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]

2.思路讲解

由于链表已排序，重复元素必然相邻。我们可以使用一个预先指针 prev 指向 potentially 要保留的节点的前一个节点，curr 指针遍历链表。

如果 curr 与 curr.next 值相同，则移动 curr 直到找到最后一个重复元素，然后将 prev.next 指向 curr.next (即跳过所有重复元素)。否则，移动 prev 和 curr。

使用哑节点可以简化边界条件的处理。

3.Java 代码实现

public class RemoveDuplicatesFromSortedListII {

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

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

    public static ListNode deleteDuplicates(ListNode head) {
        // 创建哑节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        // 初始化 prev 和 curr 指针
        ListNode prev = dummy;
        ListNode curr = head;

        while (curr != null) {
            // 判断是否有重复元素
            while (curr.next != null && curr.val == curr.next.val) {
                curr = curr.next; // 移动 curr 到最后一个重复元素
            }

            if (prev.next == curr) { // 没有重复元素
                prev = curr; // 移动 prev
            } else { // 有重复元素
                prev.next = curr.next; // 跳过所有重复元素
            }

            curr = curr.next; // 移动 curr 到下一个 potentially 要保留的节点
        }

        return dummy.next; // 返回新的头节点
    }

    // 测试代码
    public static void main(String[] args) {
        // 示例 1
        ListNode head1 = buildLinkedList(new int[]{1, 2, 3, 3, 4, 4, 5});
        ListNode result1 = deleteDuplicates(head1);
        printLinkedList(result1); // 输出：1 2 5

        // 示例 2
        ListNode head2 = buildLinkedList(new int[]{1, 1, 1, 2, 3});
        ListNode result2 = deleteDuplicates(head2);
        printLinkedList(result2); // 输出：2 3

        // 示例 3：空链表
        ListNode head3 = buildLinkedList(new int[]{});
        ListNode result3 = deleteDuplicates(head3);
        printLinkedList(result3); // 输出：

        // 示例 4：单节点链表
        ListNode head4 = buildLinkedList(new int[]{1});
        ListNode result4 = deleteDuplicates(head4);
        printLinkedList(result4); // 输出: 1

    }

    // 辅助函数：构建链表
    private static ListNode buildLinkedList(int[] values) {
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;
        for (int val : values) {
            curr.next = new ListNode(val);
            curr = curr.next;
        }
        return dummy.next;
    }


    // 打印链表
    private static void printLinkedList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }
}

4.代码解释

ListNode 类定义了链表节点的结构。
deleteDuplicates 函数实现了有序链表去重（重复元素不保留）的功能。
哑节点 dummy 简化边界条件处理。
prev 指针指向 potentially 要保留的节点的前一个节点。
curr 指针用于遍历链表。
内层 while 循环找到最后一个重复元素。
if 语句判断是否有重复元素。
prev.next = curr.next; 跳过所有重复元素。
最后返回 dummy.next。

5.复杂度分析

时间复杂度: O(n)，其中 n 是链表的长度。我们最多遍历链表一次。
空间复杂度: O(1)，我们只使用了常数个额外变量。

6.其他方法(无)

6.1 递归实现

思路分析：

递归函数负责返回：从当前节点（我）开始，完成去重的链表

若我与 next 重复，一直找到下一个不重复的节点，以它的返回结果为准
若我与 next 不重复，返回我，同时更新 next

//伪代码分析
deleteDuplicates(ListNode p = 1) {
    // 找下个不重复的
    deleteDuplicates(ListNode p = 1) {
        deleteDuplicates(ListNode p = 1) {
            deleteDuplicates(ListNode p = 2) {
                2.next=deleteDuplicates(ListNode p = 3) {
                    // 只剩一个节点，返回
                    return 3
                }
                return 2
            }
        }
    }
}

代码实现：

public ListNode deleteDuplicates(ListNode p) {
    if (p == null || p.next == null) {
        return p;
    }
    if (p.val == p.next.val) {
        ListNode x = p.next.next;
        while (x != null && x.val == p.val) {
            x = x.next;
        }
        return deleteDuplicates(x);
    } else {
        p.next = deleteDuplicates(p.next);
        return p;
    }
}

6.2 多指针实现

思路分析：

p1 是待删除的上一个节点，每次循环对比 p2、p3 的值

如果 p2 与 p3 的值重复，那么 p3 继续后移，直到找到与 p2 不重复的节点，p1 指向 p3 完成删除
如果 p2 与 p3 的值不重复，p1，p2，p3 向后平移一位，继续上面的操作
p2 或 p3 为 null 退出循环
- p2 为 null 的情况，比如链表为 1 1 1 null

s为哨兵节点
-------------------------step1----------------------------
p1 p2 p3
|  |  |
s, 1, 1, 1, 2, 3, null

-------------------------step2----------------------------
p1 p2    p3
|  |     |
s, 1, 1, 1, 2, 3, null

-------------------------step3----------------------------
p1 p2       p3
|  |        |
s, 1, 1, 1, 2, 3, null

-------------------------step4----------------------------
p1 p3
|  |
s, 2, 3, null

-------------------------step5----------------------------
p1 p2 p3
|  |  |
s, 2, 3, null

-------------------------step6----------------------------
   p1 p2 p3
   |  |  |
s, 2, 3, null

代码实现：

public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode s = new ListNode(-1, head);
    ListNode p1 = s;
    ListNode p2;
    ListNode p3;
    while ((p2 = p1.next) != null && (p3 = p2.next) != null) {
        if (p2.val == p3.val) {
            while ((p3 = p3.next) != null 
                   && p3.val == p2.val) {
            }
            p1.next = p3;
        } else {
            p1 = p1.next;
        }
    }
    return s.next;
}