ANSWERS TO "Be Prepared" AB-1, Part 2, Question 1


private ListNode split()
{
    ListNode node = myCardsList;
    for(int k = 1; k < (numCards+1)/2; k++)
        node = node.getNext();
    ListNode temp = node.getNext();
    node.setNext(null);
    return temp;
}

private ListNode combine(ListNode list1, ListNode list2)
{
    ListNode node1 = list1, node2 = list2;
    ListNode result = null, tail = null;
    
    while(node1 != null || node2 != null)
    {
        if(node1 != null)
        {
            if(tail == null)
                result = node1;
            else
                tail.setNext(node1);
            tail = node1;
            node1 = node1.getNext();
        }
        
        if(node2 != null)
        {
            if(tail == null)
                result = node2;
            else
                tail.setNext(node2);
            tail = node2;
            node2 = node2.getNext();
        }
    }
    
    tail.setNext(null);
    return result;
}

public void shuffle(int numTimes)
{
    for(int k=1; k <= numTimes; k++)
    {
        ListNode secondHalf = split();
        myCardsList = combine(secondHalf, myCardsList);
    }
}