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

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

示例 1:

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

示例 2:

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

提示：

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

解题思路

若出现重复节点
定义一个辅助节点pre，可避免单独讨论头结点的情况
将目标节点cur挂载在此节点下，即pre为cur的头节点
当链表中有元素相等时，进行遍历，一直到不相等为止跳出循环
这个时候cur的值为最后一次重复节点的值，取它的下一个节点作为不重复的值
将这个不重复的值拼在pre上，遍历下一个即可

若不重复
直接复制继续遍历即可

实现代码

package com.blog.leetcode;


/**
 * @Author Daniel
 * @Date: 2022/11/29 16:00
 * @Description LeetCode82.删除排序链表中的重复元素 II
 **/
public class Solution {
    public 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;
        }
    }

    // 删除排序链表中的重复元素
    public static ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 辅助头节点，值可以任意取
        ListNode headR = new ListNode(0);
        // 将目标链表挂载在辅助头结点下
        headR.next = head;
        // 辅助链表
        ListNode pre = headR;
        // 目标链表
        ListNode cur = head;

        while (cur != null) {
            // 相等时
            if (cur.next != null && cur.val == cur.next.val) {
                // 循环，一直到不相等后退出
                while (cur.next != null && cur.val == cur.next.val) {
                    cur = cur.next;
                }
                // 退出后的cur的值为重复节点的最后一个值，所以得再往后推一个值
                cur = cur.next;
                // 将不重复的值挂在pre节点下
                pre.next = cur;
                // 不等时，直接赋值，继续遍历
            } else {
                pre = cur;
                cur = cur.next;
            }
        }
        // 返回时，去掉头结点0
        return headR.next;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 1, 2, 3};
        ListNode root = array2ListNode(arr);
        ListNode deleteNode = deleteDuplicates(root);
        printListNode(deleteNode);

    }

    // 数组转链表
    private static ListNode array2ListNode(int[] arr) {
        ListNode root = new ListNode(arr[0]);
        // 为了不改变节点本身的值，创建一个child节点用来给子节点赋值
        ListNode child = root;
        for (int i = 1; i < arr.length; i++) {
            ListNode newNode = new ListNode(arr[i]);
            // 调用.next方法将新节点传递给child节点
            child.next = newNode;
            // 将新节点作为下一次循环的父节点
            child = newNode;
        }
        return root;
    }

    // 打印链表
    private static void printListNode(ListNode deleteNode) {
        while (deleteNode != null) {
            System.out.println(deleteNode.val);
            deleteNode = deleteNode.next;
        }
    }


}