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

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指针完成所以不会存在超出时间限制的问题。