StackStalk
  • Home
  • Java
    • Java Collection
    • Spring Boot Collection
  • Python
    • Python Collection
  • C++
    • C++ Collection
    • Progamming Problems
    • Algorithms
    • Data Structures
    • Design Patterns
  • General
    • Tips and Tricks

Sunday, August 16, 2020

Find a loop in linked list and identify the looped node

 August 16, 2020     Programming problems in CPP     No comments   

In this case, the linked list has tail joined back in to the list forming a loop. Identify the looped node. For example A->B->C->D->E->F->G->H->I-NULL, has been modified so that I's next is pointing to, let us say D. Task is to identify D. Alternatively, another question would be to find I and set it's next to NULL to correct the linked list.

Approach to find a loop in a linked list

  1. First identify the loop (using fast and slow pointer method). Thereby identifying a node in the loop
  2. Find the loop length.
  3. Now start two pointers one at the head (first) of the list and another (second) at the node at loop length distance from head. Increment both simultaneously until they meet each other. If A is the length from head to the looped node and B is the loop length. A+B is the length of original linked list. Hence when the second moves by B+A length, the first one would have moved by A and hence they meet each other.

If you don't have to find the loop length, or otherwise one could start one pointer to head and the second (faster pointer) start from where they met. This time second pointer moving at the same speed at the first one (-->see findJoinedNode function). findJoinedNode works better than the findJoinedNodeWithLoopLength.

C++ program to find a loop in a linked list

#include <iostream>
using namespace std;

// List nodeclass
class Node {
public:
    int data;
    Node* next;
};

// Linked list class
class List {
public:
    List() { head = NULL; tail = NULL;}
    ~List() {}
    Node* addNode(int val);
    void print();
    Node* findJoinedNode();
    Node* findJoinedNodeWithLoopLength();

private:
    Node* head;
    Node* tail;
};

// Function to add a node to the list
Node* List::addNode(int val)
{
    Node* temp = new Node();
    temp->data = val;
    temp->next = NULL;

    if ( tail == NULL ) {
        tail = temp;
        head = temp;
    }
    else {
        tail->next = temp;
        tail = temp;
    }
    return temp;
}

void List::print()
{
    Node* temp = head;
    int ctr = 0;
    while ( (temp != NULL) && (ctr++ != 25)  ) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << endl;
}


Node* List::findJoinedNode()
{
    Node* ptr1 = head;
    Node* ptr2 = head;

    // First find the loop.
    while( ptr2->next != NULL )
    {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next->next;
        if (ptr1 == ptr2)
            break;
    }

    if (ptr2->next == NULL)
    {
        return NULL;
    }

    ptr1 = head;

    while (ptr1 != ptr2) {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }

    return ptr1;
}

Node* List::findJoinedNodeWithLoopLength()
{
    Node* ptr1 = head;
    Node* ptr2 = head;

    // First find the loop.
    while( ptr2->next != NULL )
    {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next->next;
        if (ptr1 == ptr2)
            break;
    }
    if (ptr2->next == NULL)
    {
        cout << "No loop exists!" << endl;
        return NULL;
    }
    cout << "loop length: ";
    // find the loop length.
    int loopLength = 0;
    while (ptr2->next != ptr1) {
        loopLength++;
        ptr2 = ptr2->next;
    }
    loopLength++;
    cout << loopLength <<endl;

    ptr1 = head;
    ptr2 = head;

    while (loopLength--) {
        ptr2 = ptr2->next;
    }
    while (ptr1 != ptr2) {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }

    return ptr1;
}


// Test program
int main() {
    List* list = new List();
    list->addNode(1);
    list->addNode(2);
    list->addNode(3);
    list->addNode(4);
    list->addNode(5);
    Node* join = list->addNode(6);
    list->addNode(7);
    list->addNode(8);
    list->addNode(9);
    list->addNode(10);
    list->addNode(11);
    list->addNode(12);
    Node* tail = list->addNode(13);

    cout << "original list: " << endl;
    list->print();
    // create a circular list.
    tail->next = join;
    cout << "After list is made circular, 25 node traversal of linked list gives: " << endl;
    list->print();

    Node* jn = list->findJoinedNodeWithLoopLength();

    if (jn != NULL)
        cout << "Joined node data: " << jn->data << endl;

    delete list;
}
Output:-
original list:
1 2 3 4 5 6 7 8 9 10 11 12 13
After list is made circular, 25 node traversal of linked list gives:
1 2 3 4 5 6 7 8 9 10 11 12 13 6 7 8 9 10 11 12 13 6 7 8 9
loop length: 8
Joined node data: 6
  • Share This:  
Newer Post Older Post Home

0 comments:

Post a Comment

Follow @StackStalk
Get new posts by email:
Powered by follow.it

Popular Posts

  • Avro Producer and Consumer with Python using Confluent Kafka
    In this article, we will understand Avro a popular data serialization format in streaming data applications and develop a simple Avro Produc...
  • Monitor Spring Boot App with Micrometer and Prometheus
    Modern distributed applications typically have multiple microservices working together. Ability to monitor and manage aspects like health, m...
  • Server-Sent Events with Spring WebFlux
    In this article we will review the concepts of server-sent events and work on an example using WebFlux. Before getting into this article it ...
  • Implement caching in a Spring Boot microservice using Redis
    In this article we will explore how to use Redis as a data cache for a Spring Boot microservice using PostgreSQL as the database. Idea is to...
  • Python FastAPI microservice with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Spring Boot with Okta and OPA
    Authentication (AuthN) and Authorization (AuthZ) is a common challenge when developing microservices. In this article, we will explore how t...
  • Getting started with Kafka in Python
    This article will provide an overview of Kafka and how to get started with Kafka in Python with a simple example. What is Kafka? ...
  • Getting started in GraphQL with Spring Boot
    In this article we will explore basic concepts on GraphQL and look at how to develop a microservice in Spring Boot with GraphQL support. ...

Copyright © StackStalk