Remove Duplicates from Unsorted List

Remove Duplicates from Unsorted List

Write code to remove duplicates from an unsorted linked list

FOLLOW UP

How would you solve this problem if a temporary buffer is not allowed?

Solution

根据题意进行删除即可

Complexity

时间复杂度 O(n)，空间复杂度 O(n)

Code

public static Node removeDups(Node head){
    HashSet<Integer> intSet = new HashSet<Integer>();
    Node cur = head;
    Node previous = null;
    while (cur != null){
        if (intSet.contains(cur.data)){
            previous.next = cur.next;
        }
        else{
            intSet.add(cur.data);
            previous = cur;
        }
        cur = cur.next;
    }
    return head;
}

/**
 * Iterate with two pointer: one iterates through the linked list, and the
 * other checks all subsequent nodes for duplicates
 */
public static Node removeDupsNoExtraSpace(Node head){
    Node cur = head;
    while (cur != null){
        Node pointer = cur;
        while (pointer.next != null){
            if (pointer.next.data == cur.data){
                pointer.next = pointer.next.next;
            }
            else {
                pointer = pointer.next;
            }
        }
        cur = cur.next;
    }

    return head;
}