// Stores integers.
// No duplicates allowed.
// Increasing sorted order
class SortedLinkedList
{
    private class Node
    {
        public Node( int d, Node n )
        {
            data = d;
            next = n;
        }

        int data;
        Node next;
    }

    public void clear( )
    {
        first = null;
    }

    public boolean isEmpty( )
    {
        return first == null;
    }

    public SortedLinkedList( )
    {
        first = null;
    }

    public boolean add( int x )
    {
        if( isEmpty( ) )
        {
            first = new Node( x, null );
            return true;
        }

        // List is definitely NOT empty
        // Check if x is new minimum in the list
        if( x < first.data )
        {
            first = new Node( x, first );
            return true;
        }

        // Step #1: Find last item <= x
        Node p = first;
        while( p.next != null && p.next.data <= x )
            p = p.next;

        // Step #2: Check for duplicates
        if( p.data == x )
            return false;

        // Step #3: Splice in new node
        p.next = new Node( x, p.next );
        return true;
    }


    private Node lastNodeInResult = null;

    private void moveToEndOfResult( int x, SortedLinkedList result )
    {
        if( lastNodeInResult == null )
        {
            lastNodeInResult = new Node( x, null );
            result.first = lastNodeInResult;
        }
        else
        {
            lastNodeInResult.next = new Node( x, null );
            lastNodeInResult = lastNodeInResult.next;
        }
    }

    public SortedLinkedList merge( SortedLinkedList other )
    {
        Node p = first;
        Node q = other.first;

        SortedLinkedList result = new SortedLinkedList( );

        while( p != null && q != null )
        {
            if( p.data < q.data )
            {
                // move p.data into result
                moveToEndOfResult( p.data, result );
                p = p.next;
            }
            else if( p.data > q.data )
            {
                // move q.data into result
                moveToEndOfResult( q.data, result );
                q = q.next;
            }
            else
            {
                // duplicate pick one move into result
                moveToEndOfResult( p.data, result );
                p = p.next;
                q = q.next;
            }
        }

        // Either p is null or q is null (or both are null)
        while( p != null )
        {
            moveToEndOfResult( p.data, result );
            p = p.next;
        }

        while( q != null )
        {
            moveToEndOfResult( q.data, result );
            q = q.next;
        }

        return result;
    }

    public boolean contains( int x )
    {
        for( Node p = first; p != null; p = p.next )
            if( p.data == x )
                return true;

        return false;
    }

    public boolean remove( int x )
    {
        throw new UnsupportedOperationException( );
    }

    public boolean equals( Object other )
    {
        if( !( other instanceof SortedLinkedList ) )
            return false;

        SortedLinkedList rhs = (SortedLinkedList) other;

        Node p = first;
        Node q = rhs.first;

        for( ; p != null && q != null; p = p.next, q = q.next )
            if( p.data != q.data )
                return false;

        return p == null && q == null;
    }

    public String toString( )
    {
        String result = "[ ";

        for( Node p = first; p != null; p = p.next )
            result += p.data + " ";

        result += "]";

        return result;
    }

    private Node first;
}

class MyListDemo
{
    public static void main( String [ ] args )
    {
        SortedLinkedList list = new SortedLinkedList( );

        list.add( 4 );
        list.add( 10 );
        list.add( 0 );
        list.add( 4 );
        list.add( 0 );
        list.add( 50 );

        System.out.println( list );

        for( int i = 0; i < 15; i++ )
            System.out.println( "contains(" + i + "): " + list.contains( i ) );

        SortedLinkedList list2 = new SortedLinkedList( );
        list2.add( 5 );
        list2.add( 2 );
        list2.add( 10 );
        list2.add( 4 );
        System.out.println( list );
        System.out.println( list2 );
        System.out.println( list.merge( list2 ) );
    }

}