// D. Scott
// CCI - Problem 2.1
// Delete duplicate entries from a linked list
// -- uses buffer linked list

import java.util.Scanner;

class Node {
    Node next = null;
    int data;
    
    public Node(int d) {
        data = d;
    }

    
    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }
}

public static void main (String[] args)
{
    Node list1 = new Node(26);
    Node l1head = list1;   // head of our list (pass to delete)
    Node buffer = new Node(0);  // list of seen nodes
    Node bhead = buffer;  // head of buffer
    
    // create list with duplicates
    list1.appendToTail(33);
    list1.appendToTail(36);
    list1.appendToTail(143);
    list1.appendToTail(12);
    list1.appendToTail(33);
    list1.appendToTail(12);
    list1.appendToTail(19);
    
    // print list
    System.out.println("List contents:");
    int count = 1;
    while (list1 != null) {
        System.out.println(count + ". " + list1.data);
        
        // check buffer for duplicates
        boolean found = false;
        while (buffer != null) {
            // if found in buffer, duplicate (-> delete)
            if (buffer.data == list1.data) {
                deleteNode(l1head,list1.data);
                found = true;
            }
            buffer = buffer.next;
        }
        buffer = bhead;
        // if not found in buffer, add it
        if (found == false) {
            buffer.appendToTail(list1.data);
        }
        
        count++;
        list1 = list1.next;
    }
    // reset counter and reset list to point at head
    count = 1;
    list1 = l1head;

    System.out.println("\nRevised list (duplicates removed):");
    while (list1 != null) {
        System.out.println(count + ". " + list1.data);
        count++;
        list1 = list1.next;
    }
}

Node deleteNode(Node head, int d) {
    if (head == null) return null;
    Node n = head;
    
    if (n.data == d) {
        return head.next;
    }
    
    while (n.next != null) {
        if (n.next.data == d) {
            n.next = n.next.next;
            return head;
        }
        n = n.next;
    }
    return head;
}

// D. Scott
// CCI - Problem 2.1 FOLLOW UP
// Delete duplicate entries from a linked list
// -- does not use temporary buffer

import java.util.Scanner;

class Node {
    Node next = null;
    int data;
    
    public Node(int d) {
        data = d;
    }

    
    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }
}

public static void main (String[] args)
{
    Node list1 = new Node(26);
    Node l1head = list1;   // head of our list (pass to delete)
    
    // create list with duplicates
    list1.appendToTail(33);
    list1.appendToTail(36);
    list1.appendToTail(143);
    list1.appendToTail(12);
    list1.appendToTail(33);
    list1.appendToTail(12);
    list1.appendToTail(19);
    list1.appendToTail(33);
    
    // print list
    System.out.println("List contents:");
    int count = 1;
    while (list1 != null) {
        System.out.println(count + ". " + list1.data);
        list1 = list1.next;
        count++;
    }

    list1 = l1head;
    count = 1;
    
    // Duplicate check:
    while (list1 != null) {
        Node curr = list1.next;
        while (curr != null) {
            if (list1.data == curr.data) {
                deleteNode(l1head,list1.data);
                System.out.println("Duplicate detected.  Deleted " +
                                  list1.data);
            }
            curr = curr.next;
        }        
        count++;
        list1 = list1.next;
    }
    // reset counter and reset list to point at head
    count = 1;
    list1 = l1head;

    System.out.println("\nRevised list (duplicates removed):");
    while (list1 != null) {
        System.out.println(count + ". " + list1.data);
        count++;
        list1 = list1.next;
    }
}

Node deleteNode(Node head, int d) {
    if (head == null) return null;
    Node n = head;
    
    if (n.data == d) {
        return head.next;
    }
    
    while (n.next != null) {
        if (n.next.data == d) {
            n.next = n.next.next;
            return head;
        }
        n = n.next;
    }
    return head;
}