Skip to content
  • Linkedin
  • Youtube
  • Pinterest
  • Home
  • Privacy Policy
  • About
  • Contact
Programmingoneonone

Programmingoneonone

Programmingoneonone is a website that publishes daily tutorials, methods, guides, and articles on IT, Education, and technology.

  • Home
  • Human Values
  • DSA
  • IoT Tutorials
  • Interview Questions and Answers
  • Toggle search form
find and remove loop in linked list

Find and remove the loop in a linked list

Posted on 12 May 202022 April 2023 By YASH PAL No Comments on Find and remove the loop in a linked list

To find a loop or cycle and remove it from a linked list we have two approaches.

  1. Using the visited flag in each node.
  2. Hare and Tortoise/ Floyd’s cycle detection algorithm

Using the visited flag method to find a loop in a linked list

using this method we set a flag to value true for each node that visited the first time. and if we visit the node again that has a flag set to value true then the list has a loop and if not then the list has not any cycle or loop. 

but using this method we need to update the whole list so that is why we don’t use this method to find a loop in the list.

instead, we use the hare and tortoise algorithm to find the cycle in the list.

Hare and Tortoise algorithm to find a loop in the linked list.

this algorithm is also called Floyd’s cycle detection algorithm. in this algorithm, we use two reference tortoises and a hare. in the beginning, both reference hare and tortoise are set to the first node of the linked list. 

in every iteration, the hare reference visits two nodes at a time and the tortoise reference visits a single node at a time. and if both references meet on the same node then the list has a loop and if not then the list does not have any loop.

let’s understand the algorithm with an example

let’s say we have a linked list that has 8 nodes. as you see in the image given below. and it has a cycle in it.

find and remove loop in linked list

so first we set two references hare and tortoise and at the beginning of the iteration, we set both references to the first node of the list.

find and remove loop in linked list

as we know the tortoise reference visits one node at a time and the hare reference visits two nodes at a time.

find and remove loop in linked list
find and remove loop in linked list
find and remove loop in linked list
find and remove loop in linked list

so now both the reference meets at the same node then the list has a cycle.

def has_cycle(self):
    if self.find_cycle() is None:
        return False    else:
        return True
def find_cycle(self):
    if self.start is None or self.start.link is None:
        return None
    slowR = self.start
    fastR = self.start

    while fastR is not None and fastR.link is not None:
        slowR = slowR.link
        fastR = fastR.link.link
        if slowR == fastR:
            return slowR
    return None

To remove a loop in the linked list first we need to find the length of the loop in the linked list and then we need to find the length of the rest of the linked list and then we the length of the loop and length of the rest of the linked list. so we get the whole length of the list and then we place the null or None at the last node of the list.

Remove the loop in a linked list

after we can find the reference p and q.

find and remove loop in linked list

First, we need to find the length of a loop in the linked list.

Length of the loop in the linked list

so to find the length of the loop in the linked list we traverse one reference one node at a time among both references and we count the number of nodes that traverse by the reference.

and when the one reference value becomes equal to the second reference then we stop traversing. and the number of nodes that a reference traverses is the length of the loop in the linked list.

as you see we move the q reference one node at a time and count the number of nodes that the q variable traverse before the value of node q becomes equal to the node p.

find and remove loop in linked list
find and remove loop in linked list
find and remove loop in linked list
find and remove loop in linked list
find and remove loop in linked list

so after traversing the 5 nodes the value of node q become equal to the value of node p. So the length of the loop in the linked list is 5. now we need to find the length of the rest of the linked list.

Length of the rest of the linked list

to find the length of the rest of the linked list first, we place a reference to the first node of the list among both of the references. As you see in the image given below we place the reference to the first node of the list.

find and remove loop in linked list

now we traverse one node at a time using both of the references in the list until both references meet at the same node and count the number of nodes traverse by anyone reference. as you see in the image given below.

find and remove loop in linked list
find and remove loop in linked list
find and remove loop in linked list

as you see after traversing the three nodes both references meet at the same node. so now the number of nodes that traverse by anyone reference has become the remaining length of the list.

so now the length of the whole list is equal to the length of the cycle plus the length of the remaining list.
in the above example, the total length of the list is equal to 5+3=8.

now we place the Null or None value in the linked part of the 8th node. as you see in the image given below.

find and remove loop in linked list

so now we remove the loop from the list.

def remove_cycle(self):
    c = self.find_cycle()
    if c is None:
        return
    print("Node at which the cycle was detected is ", c.info)

    p = c
    q = c
    len_cycle = 0
    while True:
        len_cycle+=1
        q = q.link
        if p == q:
            break
    print("Length of cycle is :", len_cycle)

    len_rem_list = 0
    p = self.start
    while p != q:
        len_rem_list+=1
        p = p.link
        q = q.link

    print("Number of nodes not included in the cycle are : ", len_rem_list)
    length_list = len_cycle + len_rem_list
    print("Length of the list is : ", length_list)

    p = self.start
    for i in range(length_list-1):
        p = p.link
    p.link = None
Computer Science Tutorials, Data Structures Tutorials Tags:computer science, Data Structure

Post navigation

Previous Post: Sorting a Linked list in Data structures
Next Post: Doubly linked list in Data Structure

Related Tutorials

Reading input in c programming Reading Input in a C program C Programming Tutorials
The First C Program C Programming Tutorials
Compiling C Programs C Programming Tutorials
History of c programming language HISTORY OF C Programming Language C Programming Tutorials
c character sets C Character Sets C Programming Tutorials
c programming interview questions and answers C Programming Interview Questions and Answers C Programming Tutorials

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

Pick your Subject

  • Internet of Things
  • Data Structures/Algorithms
  • Interview Preparation
  • Human Values
  • Java Interview Questions and Answers (2023)
    Thinking of becoming a Java developer? I must say it’s a good choice! Java is continuously named the most popular programming language. And the...

    Learn More “Java Interview Questions and Answers (2023)” »

  • Iot(Internet of things) in healthcare
    IoT in Healthcare
    IoMT (Internet of Medical Things) stands for devices that can collect and exchange data – either with users or other devices via the internet,...

    Learn More “IoT in Healthcare” »

  • four stages of iot solution for industry
    IoT for Industry
    In this post, we are going to learn about use cases of IoT for Industry and four stages for providing IoT solutions. Machine Diagnosis...

    Learn More “IoT for Industry” »

  • Iot for agricultural
    IoT in Agriculture
    IoT technology has realized smart wearables, connected devices, automated machines, and driverless cars. However, in agriculture, the IoT has brought the greatest impact. Amongst the challenges...

    Learn More “IoT in Agriculture” »

  • Iot for logistics
    IoT in Logistics and Supply Chain
    IoT applications for smart logistics and supply chain systems:  Logistics Fleet Tracking  To track the locations of the vehicles in real time, the vehicle...

    Learn More “IoT in Logistics and Supply Chain” »

  • Algorithms Tutorials
  • Basic Programming
  • C Programming Tutorials
  • C++ Tutorials
  • Compiler Design Tutorials
  • Computer Networks Tutorials
  • Computer Organization Tutorials
  • Computer Science Tutorials
  • Data Structures Tutorials
  • DBMS Tutorials
  • Developer Guide
  • Digital Communication
  • Digital Logic Tutorials
  • Internet of Things Tutorials
  • Internet Tutorials
  • Interview questions answers
  • Java Tutorials
  • Javascript Tutorials
  • Machine Learning Tutorials
  • Operating Systems Tutorials
  • Programming Tutorials
  • Projects
  • Tips&Tricks
  • Tools
  • VBScript Tutorials
  • Java Interview Questions and Answers (2023)
    Thinking of becoming a Java developer? I must say it’s a good choice! Java is continuously named the most popular programming language. And the...

    Learn More “Java Interview Questions and Answers (2023)” »

  • Iot(Internet of things) in healthcare
    IoT in Healthcare
    IoMT (Internet of Medical Things) stands for devices that can collect and exchange data – either with users or other devices via the internet,...

    Learn More “IoT in Healthcare” »

  • four stages of iot solution for industry
    IoT for Industry
    In this post, we are going to learn about use cases of IoT for Industry and four stages for providing IoT solutions. Machine Diagnosis...

    Learn More “IoT for Industry” »

  • Iot for agricultural
    IoT in Agriculture
    IoT technology has realized smart wearables, connected devices, automated machines, and driverless cars. However, in agriculture, the IoT has brought the greatest impact. Amongst the challenges...

    Learn More “IoT in Agriculture” »

  • Iot for logistics
    IoT in Logistics and Supply Chain
    IoT applications for smart logistics and supply chain systems:  Logistics Fleet Tracking  To track the locations of the vehicles in real time, the vehicle...

    Learn More “IoT in Logistics and Supply Chain” »

Copyright © 2023 Programmingoneonone.

Powered by PressBook Blog WordPress theme