// D. Scott
// CCI - Problem 2.6
// Determine whether the contents of a linked list constitute a palindrome.

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(5);
    Node head = list1;
    list1.appendToTail(3);
    list1.appendToTail(8);
    list1.appendToTail(6);
    list1.appendToTail(6);
    list1.appendToTail(8);
    list1.appendToTail(3);
    list1.appendToTail(5);
    
    Node list2 = new Node(0);
    Node l2_head = list2;
    Node l2 = new Node(0);
    
    // Calculate size of list and print contents
    int size = 0;
    System.out.println("List contents: ");
    while (list1 != null) {
        size++;
        System.out.print(list1.data + " ");
        list1 = list1.next;
    }
    list1 = head;

    // Copy first half of elements to second list
    int count = 0;
    while (count < size/2) {
        if (count == 0) 
            list2.data = list1.data;
        else
            list2.appendToTail(list1.data);
        list1 = list1.next;
        count++;
    }

    
    // Reverse first half of list and compare to second half
    reverseList(list2,l2);
    l2 = l2.next;
    
    boolean isPal = true;
    while (l2 != null) {
        if (l2.data != list1.data) {
            isPal = false;
            break;
        }
        l2 = l2.next;
        list1 = list1.next;
    }

    
    // Print results
    if (isPal == true) {
        System.out.println("\nThe list is a palindrome.");
    } else {
        System.out.println("\nThe list is not a palindrome.");
    }    
    
}

void reverseList(Node l, Node r) {
    if (l == null)
        return;
    reverseList(l.next,r);

    r.appendToTail(l.data);
}

// D. Scott
// CCI - Problem 2.6
// Determine whether the contents of a linked list constitute a palindrome.

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(5);
    Node head = list1;
    list1.appendToTail(3);
    list1.appendToTail(8);
    list1.appendToTail(6);
    list1.appendToTail(6);
    list1.appendToTail(8);
    list1.appendToTail(7);
    list1.appendToTail(5);
    
    Node list2 = new Node(0);
    Node l2_head = list2;
    Node l2 = new Node(0);
    
    // Calculate size of list and print contents
    int size = 0;
    System.out.println("List contents: ");
    while (list1 != null) {
        size++;
        System.out.print(list1.data + " ");
        list1 = list1.next;
    }
    list1 = head;

    // Copy first half of elements to second list
    int count = 0;
    while (count < size/2) {
        if (count == 0) 
            list2.data = list1.data;
        else
            list2.appendToTail(list1.data);
        list1 = list1.next;
        count++;
    }

    
    // Reverse first half of list and compare to second half
    reverseList(list2,l2);
    l2 = l2.next;
    
    boolean isPal = true;
    while (l2 != null) {
        if (l2.data != list1.data) {
            isPal = false;
            break;
        }
        l2 = l2.next;
        list1 = list1.next;
    }

    
    // Print results
    if (isPal == true) {
        System.out.println("\nThe list is a palindrome.");
    } else {
        System.out.println("\nThe list is not a palindrome.");
    }    
    
}

void reverseList(Node l, Node r) {
    if (l == null)
        return;
    reverseList(l.next,r);

    r.appendToTail(l.data);
}