leetcode [#82]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example:
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.

---

解决方案

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null) return null;
        ListNode p = head;

        LinkedHashSet<Integer> setDuplicates = new LinkedHashSet<>();
        LinkedHashSet<Integer> setAll = new LinkedHashSet<>();

        while(p != null && p.next != null){
            if(p.val == p.next.val){
                setDuplicates.add(p.val);
            }
            p = p.next;
        }

        p = head;
        while(p != null){
            setAll.add(p.val);
            p = p.next;
        }

        Iterator<Integer> setDuplicatesIt = setDuplicates.iterator();
        while(setDuplicatesIt.hasNext()){
            setAll.remove(setDuplicatesIt.next());
        }
        
        if(setAll.size() > 0){
            ListNode result = new ListNode(0);
            ListNode q = result;
            Iterator<Integer> it = setAll.iterator();
            while(it.hasNext()){
                q.val = it.next();
                if(it.hasNext()){
                    q.next = new ListNode(0);
                    q = q.next;
                } else {
                    q.next = null;
                }
            }
            return result;
        } else {
            return null;
        }
    }
}

---

注意事项

1. 与83链表去重相比，本题要求“完全去重”，即重复元素不是保留一次，而是完全删除。
2. 这种方法用了LinkedHashSet，其特性是会去掉加入的重复元素，且与HashSet相比，可以保留元素加入的顺序不变，而不会像HashSet对加入的元素进行排序。
3. 这种方法效率较低，与83题考虑指针变化来解题的思路类似，discuss中vote较高的回答做法如下：

   public ListNode deleteDuplicates(ListNode head) {
           if(head==null) return null;
           ListNode FakeHead=new ListNode(0);
           FakeHead.next=head;
           ListNode pre=FakeHead;
           ListNode cur=head;
           while(cur!=null){
               while(cur.next!=null&&cur.val==cur.next.val){
                   cur=cur.next;
               }
               if(pre.next==cur){
                   pre=pre.next;
               } else{
                   pre.next=cur.next;
               }
               cur=cur.next;
           }
           return FakeHead.next;
   }

其思路是：

1.定义了“头指针”，也就是指向头结点的“虚拟新增结点”。这样就去除了头结点的特殊性，从而可以应对从链表一开始元素就是重复的这种情况。
2.一开始，pre指向头指针结点，cur指向头结点。从cur即头结点开始遍历整个链表。
3.如果下一结点不为空且当前节点的值和下一结点的值相等，那么cur指针向后移动一位。
4.此时考虑指针pre，如果pre就在cur前面1位，那么pre向后移动一位即可，也就是cur和pre此时指向同一元素。否则，说明cur和pre中间间隔有元素，就正是那些重复的元素，这些都应该被跳过，跳过的方法就是，让pre指向cur后面1位的元素，即pre.next=cur.next;。
5.经过上述步骤，处理完所有情况，此时cur向后移动一位，重新开始考虑上面的步骤。