Find k-th node from end in Linked List

void print_kth_from_end(Node *head, int k){

    Node *lead = head;

    Node *lag = head;

    while(k > 0){

        if(lead){

            k--;

            lead = lead->next;

        }

        else{

            std::cout << "K is larger than length of Linked List" << std::endl;

            return;

        }

    }

    while(lead){

        lead = lead->next;

        lag = lag->next;

    }

    std::cout << "kth node from end = " << lag->data << std::endl;

}

Detailed explanation can be found on Youtube:

Subscribe to KnowledgeCenter

Find the middle element of a Linked List

void print_middle(Node *head){

    Node *fast = head;

    Node *slow = head;

    while(fast && fast->next){

        fast = fast->next->next;

        slow = slow->next;

    }

    std::cout << slow->data << std::endl;

}

Watch the detailed explanation of the concepts on Youtube:

Subscribe to KnowledgeCenter

Find the Length of Loop in Linked List

We modify the Floyd's Loop/Cycle Detection Algorithm that we saw in the previous Post to find the count of Nodes which are part of the Linked List.

int count_loop_lenth(Node *node){

    int count = 1;

    Node *curr = node;

    while(curr->next != node){

        curr = curr->next;

        ++count;

    }

    return count;

}

int detect_loop_floyd(Node *head){

    Node *slow = head;

    Node *fast = head;

    while(slow && fast && fast->next){

        slow = slow->next;

        fast = fast->next->next;

        if(slow == fast){

            return count_loop_lenth(slow);

        }

    }

    return 0;

}

Watch detailed Explanation on Youtube.

Subscribe to KnowledgeCenter

Detect Loop in a Linked List

Method 1: (Hashing)

bool detect_loop_map(Node *head){

    std::unordered_map<Node*, bool> visited;

    Node *curr = head;

    while(curr){

        if (visited[curr] == true)

            return true;

        visited[curr] = true;

        curr = curr->next;

    }

    return false;

}

Method 2:(Floyd's Cycle Detection)

bool detect_loop_floyd(Node *head){

    Node *slow = head;

    Node *fast = head;

    while(slow && fast && fast->next){

        slow = slow->next;

        fast = fast->next->next;

        if (slow == fast){

            return true;

        }

    }

    return false;

}

Watch detailed explanation on Youtube:

Visit our Youtube playlist for Linked List: https://www.youtube.com/playlist?list=PL1w8k37X_6L-bwZCPpELH6Cwo3WzUxDp7

Subscribe to KnowledgeCenter