CareerCup 150

C.C 2.1

/**
 * 2.1 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?
 *
 * public class ListNode { int val; ListNode next; }
 *
 * @author Jiateng
 */
public class CC2_1 {

    //Time O(n), Space O(n)
    public static void remove1(MyLinkedList list) {

        if (list == null || list.head == null) {
            return;
        }

        Hashtable ht = new Hashtable();
        ListNode current = list.head;
        ListNode next = list.head;

        while (next != null) {
            if (ht.containsKey(next.getVal())) {
                //break the link, jump and link to the next position.
                current.setNext(next.getNext());
            } else {
                //add
                ht.put(next.getVal(), 1);
                //move curent to the position
                current = next;
            }
            //everytime move one step, go through the whole list
            next = next.getNext();
        }
    }

    //Time O(n^2), Space O(1)
    public static void remove2(MyLinkedList list) {
        if (list == null || list.head == null) {
            return;
        }

        ListNode current = list.head;

        while (current != null) {
            ListNode next = current;

            while (next.getNext() != null) {
                //if find same value, jump and link to the next 
                if (next.getNext().getVal() == current.getVal()) {
                    next.setNext(next.getNext().getNext());
                } //move to the next
                else {
                    next = next.getNext();
                }
            }
            //after compare with current node, move to the next and compare again
            current = current.getNext();
        }
    }

    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList(new int[]{1, 2, 2, 3, 3, 3, 5, 6, 4, 3, 4, 5, 6, 7}); 
        //MyLinkedList list = new MyLinkedList(new int[]{' ', 1, 1, 1, 2, 2, 3, 3, 3, 5, 6, 4, 3, 4, 5, 6, 7});
        list.print();
        //remove1(list);
        remove2(list);
        list.print();
    }
}



*****Model*****
public class ListNode {

    public int val;
    public ListNode next;

    public ListNode(int x) {
        val = x;
        next = null;
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public ListNode getNext() {
        return next;
    }

    public void setNext(ListNode next) {
        this.next = next;
    }
}


public class MyLinkedList {

    public ListNode head;

    public MyLinkedList(ListNode h) {
        head = h;
    }

    public MyLinkedList(int[] array) {

        if (array == null || array.length == 0) {
            return;
        }

        head = new ListNode(array[0]);
        ListNode temp = head;

        for (int i = 1; i < array.length; i++) {
            temp.setNext(new ListNode(array[i]));
            temp = temp.getNext();
        }
    }

    public void print() {
        ListNode current = head;

        while (current != null) {
            System.out.print(current.getVal());
            if (current.next != null) {
                System.out.print(" -> ");
            }
            current = current.getNext();
        }
        System.out.println();
    }
}