Some Linked List stuff !

#include <iostream>
#include <iomanip>
#include <vector>
#include <set>
#include <stack>
#include <conio.h>

struct Node
{
    Node(int d)
    {
        data = d;
        next = NULL;
    }
    
    int data;
    Node* next;
};

struct List
{
    Node* head;
    int size;
    
    List():head(0),size(0)
    {
    }
    
    void add(int data)
    {
        Node* tmp = new Node(data);
        if(head)
        {
            tmp->next = head;
        }
        head = tmp;
        size++;
    }
    
    
    
    void display()
    {
        Node* tmp = head;
        while(true)
        {
            if(tmp == NULL) 
                return;
            std::cout << tmp->data << std::endl;
            tmp = tmp->next;
        }
    }
    
    void reverse()
    { // inplace reversal
        // no reverse for empty list and one element list
        if(!head || head->next == NULL)
            return;

        // special case first two elements            
        Node* p = head;
        Node* q = head->next;
        Node* tmp = head->next->next;
        q->next = p;
        p->next = NULL;
        head = q;
        // invariant: tmp points to the first element of the unreversed list
        // other list pointed by head is reversed upto Node before tmp 
        while(true)
        {
            if(!tmp) return; // 2 element list or we have reached the end
            Node* n = tmp;
            tmp = tmp->next;
            n->next = head;
            head = n;
        }
    }
    
    int nthElementFromLast(int n)
    {
        // start with q = head
        // set q at distance of l from head where l = size - n
        // size comes in handy here, if no size, we need to make 2 passes
        int l = size - n - 1;
        Node* q = head;
        while(true)
        {
            if(!q) return -1;
            if(l == 0) return q->data;
            q = q->next;
            l--;
        }
    }

    int nthElementFromLast1(int n)
    {
        // uses the algorithm of using 2 ptrs p&q
        // spaced n apart - when leading ptr q reaches last element
        // p is the nth element from last element
        Node* p = head;
        Node* q = head;
        assert(n <= size);
        for(int i = 0; i < n; i++)
            q = q->next;
            
        while(true)
        {
            if(q) q = q->next;
            if(!q) return p->data;
            p = p->next;
        }
    }
};

int binarySearch(int* a, int s, int e, int n/*needle*/)
{
    if(s >= e) return -1;
    // invariant: needle must be in the array in the range
    // s...e. if not we can safely return -1
    // this holds good for all the subproblems
    if(n < a[s] || n > a[e]) return -1;
    int m = s + ((e - s) / 2);
    if(a[m] == n) return n;
    else
    {
        if(n < a[m])
            return binarySearch(a, 0, m, n);
        else
            return binarySearch(a, m+1, e, n);
    }
}

int main()
{
    //int x = 1 << 0;
    //std::cout << x << std::endl;
    
    List l;
    l.add(10);
    l.add(20);
    l.add(30);
    l.add(40);
    l.display();
    
    // reverse
    std::cout << "after reversal " << std::endl;
    l.reverse();
    l.display();
    
    std::cout << "0th element from last element " 
        << l.nthElementFromLast1(0) << std::endl;
        
    assert(l.nthElementFromLast(0) == 40);
    assert(l.nthElementFromLast(1) == 30);
    assert(l.nthElementFromLast(2) == 20);    
    assert(l.nthElementFromLast(3) == 10);

    assert(l.nthElementFromLast1(0) == 40);
    assert(l.nthElementFromLast1(1) == 30);
    assert(l.nthElementFromLast1(2) == 20);    
    assert(l.nthElementFromLast1(3) == 10);
    
    // binary search - test
    int a[] = {1, 3, 4, 6, 8, 9, 10, 15, 16, 18};
    std::cout << binarySearch(a, 0, 9, 16) << std::endl;
    getch();
}