Determine whether given LinkedList is Cyclic or Acyclic

Determine whether given LinkedList is Cyclic or Acyclic

bool determineTermination( Node *head )
{
    Node *fast, *slow;
    fast = slow = head;
    while( true )
    {
        if( !fast || !fast->next )
            return false;
        else if( fast == slow || fast->next == slow )
            return true;
        else
        {
            slow = slow->next;
            fast = fast->next->next;
        }
    }
}

Given a singly-linked list, devise an algorithm to find the mth-to-last element of the list.

Given a singly-linked list, devise an algorithm to find the mth-to-last element of the list.

Element *findMToLastElement( Element *head, int m )
{
    Element *current, *mBehind;
    int i;

    /* Advance current m elements from beginning,
     * checking for the end of the list
     */
    current = head;
    for (i = 0; i < m; i++)
    {
       if (current->next)
       {
           current = current->next;
       } else
       {
           return NULL;
       }
    }

    /* Start mBehind at beginning and advance pointers
     * together until current hits last element
     */
    mBehind = head;
    while( current->next )
    {
       current = current->next;
       mBehind = mBehind->next;
    }

    /* mBehind now points to the element we were
    * searching for, so return it
    */
    return mBehind;
}

Implement a stack using a linked list

Implement a stack using a linked list

class Stack
{
public:
    Stack();
    ~Stack();
    void push( void *data );
    void *pop();
protected:
    // Element struct needed only internally
    typedef struct Element {
        struct Element *next;
        void *data;
    } Element;

    Element *head;
};

Stack::Stack() {
    head = NULL;
    return;
}

Stack::~Stack() {
    while( head ){
        Element *next = head->next;
        delete head;
        head = next;
    }
    return;
}

void Stack::push( void *data ){
    //Allocation error will throw exception
    Element *element = new Element;
    element->data = data;
    element->next = head;
    head = element;
    return;
}

void *Stack::pop() {
    Element *popElement = head;
    void *data;

    /* Assume StackError exception class is defined elsewhere */
    if( head == NULL )
        throw StackError( E_EMPTY );

    data = head->data;
    head = head->next;
    delete popElement;
    return data;
}