牛客在线编程101-16 删除有序链表中重复的元素-II

落日映苍穹つ 2023-10-04 19:39 9阅读 0赞

### 题目 ###

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。  
例如：  
给出的链表为1 \\to 2\\to 3\\to 3\\to 4\\to 4\\to51→2→3→3→4→4→5, 返回1\\to 2\\to51→2→5.  
给出的链表为1\\to1 \\to 1\\to 2 \\to 31→1→1→2→3, 返回2\\to 32→3.

数据范围：链表长度 0 \\le n \\le 100000≤n≤10000，链表中的值满足 |val| \\le 1000∣val∣≤1000  
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)  
进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

### 解析 ###

新链表的头可能改变，需要设置一个虚拟头节点  
比较头节点后面和后后面的元素，如果重复，需要找到最后一个重复的，把头节点链接到最后一个重复节点的前面  
遇到不重复的直接更新当前节点

import java.util.*;
    
    /*
     * public class ListNode {
     *   int val;
     *   ListNode next = null;
     * }
     */
    
    public class Solution {
        
        /**
         * 
         * @param head ListNode类 
         * @return ListNode类
         */
        public ListNode deleteDuplicates (ListNode head) {
        
            // write code here
            ListNode fake = new ListNode(1001);
            fake.next = head;
    
            ListNode cur = fake;
            while(cur != null && cur.next != null && cur.next.next != null) {
        
                //发现有重复节点
                if (cur.next.val == cur.next.next.val) {
        
                    int val = cur.next.val;
                    //找到最后一个重复节点
                    ListNode tmp = cur.next.next;
                    while (tmp.next != null && tmp.val == tmp.next.val) {
        
                        tmp = tmp.next;
                    }
                    //重新连接
                    cur.next = tmp.next;
                    //当前节点不变
                } else {
        
                    cur = cur.next;
                }
            }
            return fake.next;
        }
    }