import java.util.Iterator;
import java.util.Stack;

public class DealableList<Item> implements Iterable<Item> {
    
    private class Node {
        Item item;
        Node next;
    }
   
    private Node first;
    
    public DealableList() {}            
    
    private DealableList(Node first) {  
        this.first = first;
    }
    
    public void add(Item item) {   
        Node node = new Node();
        node.item = item;
        node.next = first;
        first = node;   
    }
    
    public Iterator<Item> iterator() {
        return new Iterator<Item>() {
            Node node = first;
            
            public boolean hasNext() {
                return (node != null);
            }
            
            public Item next() {
                Item item = node.item;
                node = node.next;
                return item;
            }
        };
    }
    
    public String toString() {
        String str = "";
        for (Item s : this) {
            str += s + "->";
        }
        return str;
    }
    
    public Stack<DealableList<Item>> deal() {
        Node firstEven = null;
        Node firstOdd = null;
        
        if (first != null) {
            firstEven = first;
            firstOdd = first.next;
            
            Node e = firstEven;
            Node o = firstOdd;
            while ((e.next != null) && o.next != null) {
                
                if (e.next.next != null) {
                    e.next = e.next.next;
                    e = e.next;
                }
                else {
                    e.next = null;
                    break;
                }
                
                if (o.next.next != null) {
                    o.next = o.next.next;
                    o = o.next;
                }
                else {
                    o.next = null;
                    break;
                }
            }
            e.next = null;
        }
        first = null;
        
        Stack<DealableList<Item>> stack = new Stack<DealableList<Item>>();
        stack.push(new DealableList<Item>(firstEven));
        stack.push(new DealableList<Item>(firstOdd));
        return stack;
    }
    
    public static void main(String[] args) {
        DealableList<Integer> list = new DealableList<Integer>();
        for (int i = 11; i >= 0; i--) {
            list.add(i);
        }
        
        System.out.println(list);
        System.out.println();

        Stack<DealableList<Integer>> stack = list.deal();
        
        System.out.println(stack.pop()); // nodes originally at odd positions
        System.out.println(stack.pop()); // nodes originally at even positions
    }
}