当前位置：首页 > article >正文

Leetcode面试经典150题-82.删除排序链表中的重复元素II

article 2024/11/14 20:12:23

之前写过这个题的基础第83题，看本文之前一定要先看懂这个Leetcode面试经典150题-82.删除排序链表中的重复元素II前序-83.删除排序链表中的重复元素_删除链表中重复的元素-CSDN博客

直接上代码了，解法都在代码里，不懂就留言或者私信

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        /**空链表或者只有1个的，不涉及这个问题，直接返回原链表即可*/
        if(head == null || head.next == null) {
            return head;
        }
        /**因为有换头的可能性，先用一个空节点作为头，这样后面出现换头也会挂在它后面，它后面最终的就是头*/
        ListNode dummy = new ListNode(-101);
        dummy.next = head;
        ListNode cur = dummy;
        ListNode next = null;
        ListNode nextNext = null;
        /**如果next节点为null，也没啥可遍历的了 */
        while(cur != null && cur.next != null && cur.next.next != null) {
            /**cur是我们确定了不会重复的节点，它的next和next.next就是接下来的两个节点
            如果两个节点不相同，就要next作为下个cur，否则两个都不要，如果后面出现很多个这个值也不要*/
            if(cur.next.val != cur.next.next.val) {
                cur = cur.next;
            } else {
                /**如果相等说明有重复，找到后面第一个不重复的*/
                int x = cur.next.val;
                /**往后一直找找到第一个和cur的next不同的节点，但是这个节点也不一定就不重复
                它还要执行if里的和它后面的节点是否相同的判断 */
                while(cur.next != null && cur.next.val == x) {
                    /**出循环的时候cur的next指向它后面第一个不相同的节点 */
                    cur.next = cur.next.next;
                }
            }
        }
        return dummy.next;

    }
}/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        /**空链表或者只有1个的，不涉及这个问题，直接返回原链表即可*/
        if(head == null || head.next == null) {
            return head;
        }
        /**因为有换头的可能性，先用一个空节点作为头，这样后面出现换头也会挂在它后面，它后面最终的就是头*/
        ListNode dummy = new ListNode(-101);
        dummy.next = head;
        ListNode cur = dummy;
        ListNode next = null;
        ListNode nextNext = null;
        /**如果next节点为null，也没啥可遍历的了 */
        while(cur != null && cur.next != null && cur.next.next != null) {
            /**cur是我们确定了不会重复的节点，它的next和next.next就是接下来的两个节点
            如果两个节点不相同，就要next作为下个cur，否则两个都不要，如果后面出现很多个这个值也不要*/
            if(cur.next.val != cur.next.next.val) {
                cur = cur.next;
            } else {
                /**如果相等说明有重复，找到后面第一个不重复的*/
                int x = cur.next.val;
                /**往后一直找找到第一个和cur的next不同的节点，但是这个节点也不一定就不重复
                它还要执行if里的和它后面的节点是否相同的判断 */
                while(cur.next != null && cur.next.val == x) {
                    /**出循环的时候cur的next指向它后面第一个不相同的节点 */
                    cur.next = cur.next.next;
                }
            }
        }
        return dummy.next;

    }
}