1、题目描述

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

示例1：

输入：head = [1,1,2]

输出：[1,2]

示例2：

输入：head = [1,1,2,3,3]

输出：[1,2,3]

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序 排列

2、解题思路：快慢指针法

由于链表是已排序的，重复元素一定是相邻的。我们可以通过快慢指针来高效删除重复节点：

1. 慢指针（prenode）：指向当前已处理好的非重复链表的最后一个节点。

2. 快指针（lastnode）：遍历链表，寻找下一个与 prenode 值不同的节点。

关键步骤：

1. 初始化 prenode 和 lastnode，均从 head 开始。

2. 遍历链表：

   • 如果 prenode.val != lastnode.val，说明 lastnode 是一个新值，将 prenode.next 指向 lastnode，然后移动 prenode。

   • 无论是否相等，lastnode 都每次向前移动一步。

3. 最后断开 prenode 与后续可能存在的重复节点的连接（prenode.next = null）。

package other;

import org.junit.Test;

import java.util.Arrays;

public class deleteDuplicates {
    @Test
    public void test() {
        ListNode node5= new ListNode(3,null);
        ListNode node4= new ListNode(3,node5);
        ListNode node3= new ListNode(2,node4);
        ListNode node2= new ListNode(1,node3);
        ListNode node1= new ListNode(1,node2);
        System.out.println();
    }
    static ListNode delete(ListNode head){
        if (head == null) return null; // 空链表直接返回
        ListNode prenode = head;       // 慢指针，指向当前非重复链表的末尾
        ListNode lastnode = head.next; // 快指针，用于遍历

        while (lastnode != null) {
            if (prenode.val != lastnode.val) { // 遇到新值
                prenode.next = lastnode;       // 将慢指针的next指向快指针
                prenode = lastnode;            // 移动慢指针到新节点
            }
            lastnode = lastnode.next;         // 快指针始终向前移动
        }
        prenode.next = null; // 断开与后面重复元素的连接（防止最后几个重复）
        return head;         // 返回头节点
    }
    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}

3、复杂度分析

• 时间复杂度：O(n)，只需遍历一次链表。

• 空间复杂度：O(1)，仅使用常数额外空间。

4、边界条件处理

1. 空链表：直接返回 null。

2. 单节点链表：无需处理，直接返回 head。

3. 全重复链表：如 [1,1,1]，最终返回 [1]（通过 prenode.next = null 断开）。