LeetCode-删除排序链表中的重复元素问题

2023-12-13 12:43:15

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

题目描述:

给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回已排序的链表 。
在这里插入图片描述
思路: 因为要删除相同元素,很容易想到定义两个指针pre,cur。cur用来遍历链表,pre用来指向cur前一个元素,如果pre的值和cur的值相等,那么删除cur指向的元素,cur指向下一个节点,如果不相等,cur指向下一个节点,pre指向cur之前指向的节点。通过这样的操作即可删除链表中重复的元素并且保留下一个。
代码:

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
         if(head==null) {
             return null;
         }   
        ListNode cur=head.next;
        ListNode pre=head;
         while(cur!=null) {
             
             if(cur.val==pre.val) {
                 ListNode curNext=cur.next;
                 pre.next=curNext;
                 cur=curNext;
            } else {
                pre=cur;
                cur=cur.next;
            } 

               
             }
            
            
         
         return head;
    }
}

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

题目描述:

给定一个已排序的链表的头 head ,删除原始链表中所有重复数字的节点,只留下不同的数字 。返回已排序的链表 。
在这里插入图片描述
思路: 这里删除元素与上一题不同,这一题要删除全部重复元素,而上一题删除的同时保留一个,从而导致上一题可以轻松通过双指针解决。我这里没有按照王道的解法,因为第一题的启发,我先对链表进行删除操作,每组重复元素保留一个,但是同时也将重复的数值按链表顺序保存到一个数组中。例如:链表[1,2,2,3,4,4]经过这趟操作后变成[1,2,3,4],同时得到[2,4]这样的数组,这个数组记录下来了仍在链表中的应该删除的重复值的节点。因此按照得到的数组再进行遍历删除,如果链表中元素值等于数组中索引指向的值则删除该节点,并且数组索引加一,这是因为经过第一次删除每个重复组只保留了一个节点在链表中,所以可以这样操作。
代码:

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head==null) {
            return null;
        }

        if(head.next==null) {
            return head;
        }

        ListNode pre=head;
        ListNode cur=head.next;
        int[] arr=new int[300];
        int index=0;
        while(cur!=null) {
            if(pre.val==cur.val) {
            //数组只记录每个重复组的一个元素
                if((index>=1&&arr[index-1]!=cur.val)||index==0) {
                    arr[index++]=cur.val;
                }
                
                ListNode curNext=cur.next;
                pre.next=curNext;
                cur=curNext;
            } else {
                pre=cur;
                cur=cur.next;
            }
            
        }

        int len=index;
        //定义头节点,方便后续删除操作
        ListNode temp=new ListNode(101);
        temp.next=head;
        pre=temp;
        cur=temp.next;
        index=0;
        
        while(cur!=null) {
        //链表中元素值等于数组中索引指向的值则删除该节点
            if(index<len&&cur.val==arr[index]) {
                ListNode curNext=cur.next;
                pre.next=cur.next;
                cur=curNext;
                index++;
            } else {
                pre=cur;
                cur=cur.next;
            }


        }       
        
        return temp.next;      
    }
}

官方题解:

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0, head);

        ListNode cur = dummy;
        while (cur.next != null && cur.next.next != null) {
            if (cur.next.val == cur.next.next.val) {
                int x = cur.next.val;
                while (cur.next != null && cur.next.val == x) {
                    cur.next = cur.next.next;
                }
            } else {
                cur = cur.next;
            }
        }

        return dummy.next;
    }
}

总结: 刚做这题我确实试过两个循环,但是超出时间限制因此放弃,应该是自己思路有问题。官方的这种方法思路就是先定义一个头节点方便后续操作,如何以一个外循环遍历链表,然后内循环用来删除全部的重复元素,因为无论遍历循环以及删除元素的循环都是使用cur指针完成所以不会存在超出时间限制的问题。

文章来源:https://blog.csdn.net/qq_45965652/article/details/134962799
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。