//
//  ListNode.java
//  
//
//  Created by Herbert J. Bernstein on 2/24/11.
//  Copyright 2011 All rights reserved.
//

public class ListNode {
    int value;
    ListNode next;
    boolean hasnext;
    
    ListNode() {
        hasnext = false;
        value = 0;
    }
    
    
    // Append a data at the end of the list 
    
    static int listappend(ListNode l, int value) {
        ListNode ln, cn;
        cn = new ListNode();
        cn.value = value;
        if (!l.hasnext) {
            l.next = cn;
            l.hasnext = true;
            return 0;
        }
        ln = l;
        while (ln.hasnext) {
            if (!ln.next.hasnext) {
                ln.next.next = cn;
                ln.next.hasnext = true;
                return 0;
            }
            ln = ln.next;
        }
        return 0;
    }
    
    // Insert data in front of the list 
    
    static int listprepend ( ListNode l, int value ){
        ListNode cn;
        cn = new ListNode();
        cn.value = value;
        if (l.hasnext) {
            cn.next = l.next;
            cn.hasnext = true;
        }
        l.next = cn;
        l.hasnext = true;
        return 0;
    }
    
    // Insert data at a particular index of a list 
    
    static int listinsert ( ListNode l, int value, long index ){
        ListNode ln, pn, cn, dn;
        long jindex;
        cn = new ListNode();
        pn = new ListNode();
        cn.value = value;
        if (!(l.hasnext)) {
            l.next = cn;
            l.hasnext = true;
            return 0;
        }
        
        // index 0 is the front of the list
        
        jindex = 0;
        if (index == 0) {
            return listprepend(l,value);
        }
        
        // scan forward past jindex-1 nodes
        
        ln = l.next;
        pn = l;
        while (ln.hasnext && jindex < index) {
            pn = ln;
            ln = ln.next;
            jindex++;
        }
        
        // If jindex is less than index-1, the current
        //  list is too short, we need to pad 
        
        while (jindex < index-1) {
            dn = new ListNode();
            pn.next = dn;
            pn.hasnext = true;
            pn = dn;
            jindex++;
        }
        
        if (pn.hasnext) {
            cn.next = ln;
            cn.hasnext = true;
        }
        pn.next = cn;
        pn.hasnext = true;
        
        return 0;
        
    }
    
    
    
    
    //print list l
    
    static int printl( ListNode l ) {
        while (l.hasnext) {
            System.out.println(l.next.value);
            l = l.next;
        }
        return 0;
    }
    
    // merge list a and b and create list c
    
    static int mergel( ListNode a, ListNode b, ListNode c) {
        
        ListNode af = a;
        ListNode bf = b;
        ListNode cn;        // next node (actual)
        ListNode cp;        // previous node (pointer)
        cp = new ListNode();
        cp.hasnext = false;
        
        while (af.hasnext && bf.hasnext) {
            cn = new ListNode();
            if (af.next.value < bf.next.value) {
                cn.value = af.next.value;
                af = af.next;
            } else {
                cn.value = bf.next.value;
                bf = bf.next;
            }
            if (cp.hasnext) {
                cp.next.next = cn;
                cp.next.hasnext = true;
            } else {
                c.next = cn;
                c.hasnext = true;
            }
            cp.next = cn;
            cp.hasnext = true;
        }
        
        if (bf.hasnext) af = bf;
        
        while (af.hasnext) {
            cn = new ListNode();
            cn.value = af.next.value;
            af = af.next;
            if (cp.hasnext) {
                cp.next.next = cn;
                cp.next.hasnext = true;
            } else {
                c.next = cn;
                c.hasnext = true;
            }
            cp.next = cn;
            cp.hasnext = true;

        }
        
        return 0;
        
        
        
    }
}