Detecting a Loop in a Singly Linked List

The naive approach requires O(N^2) time and O(N) space. Basically you store all visited nodes, and compare each of them while traversing each node.

Hint: 
The best approach uses only O(N) time and O(1) space.

Solution:

The best solution runs in O(N) time and uses O(1) space. It uses two pointers (one slow pointer and one fast pointer). The slow pointer advances one node at a time, while the fast pointer traverses twice as fast. If the list has loop in it, eventually the fast and slow pointer will meet at the same node. On the other hand, if the loop has no loop, the fast pointer will reach the end of list before the slow pointer does.

bool hasLoop(Node *head) 
{
    Node *slow = head, *fast = head;

    while (slow && fast && fast->next) 
    {
        slow = slow->next;
        fast = fast->next->next;    
        
        if (slow == fast)
            return true;
    }
    return false;
}

Pop in Linked List

Extract the data from the head node, delete the node, advance the head pointer to point at the next node in line. Uses a reference parameter since it changes the head pointer.

int Pop(struct node** headRef) 
{
    struct node* head;
    int result;
    head = *headRef;
    
    assert(head != NULL);
    
    result = head->data; // pull out the data before the node is deleted
    *headRef = head->next; // unlink the head node for the caller
    
    // Note the * -- uses a reference-pointer
    //  just like Push() and DeleteList().
    
    free(head); // free the head node
    return(result); // don't forget to return the data from the link
}

Delete Linked List

Delete the whole list and set the head pointer to NULL. There is a slight complication

inside the loop, since we need extract the .next pointer before we delete the node, since
after the delete it will be technically unavailable.

void DeleteList(struct node** headRef)
{
    struct node* current = *headRef; // deref headRef to get the real head
    struct node* next;

    while (current != NULL)
    {
        next = current->next; // note the next pointer
        free(current); // delete the node
        current = next; // advance to the next node
    }

    *headRef = NULL; // Again, deref headRef to affect the real head back in the caller.
}

GetNth() in a Linked List

int GetNth(struct node* head, int index)
{
    struct node* current = head;
    int count = 0; // the index of the node we're currently looking at
    while (current != NULL)
    {
        if (count == index) return(current->data);
        count++;
        current = current->next;
    }

    assert(0); // if we get to this line, the caller was asking
    // for a non-existent element so we assert fail.
}

Count number of times a value repeated in Linked List

int Count(struct node* head, int searchFor)
{
    struct node* current = head;
    int count = 0;
    while (current != NULL)
    {
        if (current->data == searchFor) count++;
        current = current->next;
    }
    return count;
}

Length of Linked List

// Return the number of nodes in a list (while-loop version)
int Length(struct node* head)
{
    int count = 0;
    struct node* current = head;
    while (current != NULL)
    {
        count++;
        current = current->next;
    }
    return(count);
}