# 算法题：检测并删除链表中的循环

2021年4月21日18:47:48 发表评论 628 次浏览

## CPP

``````//C++ program to detect and remove loop in linked list
#include <bits/stdc++.h>
using namespace std;

struct Node {
int data;
struct Node* next;
};

/* Function to remove loop. Used by detectAndRemoveLoop() */
void removeLoop( struct Node*, struct Node*);

/* This function detects and removes loop in the list
If loop was there in the list then it returns 1, otherwise returns 0 */
int detectAndRemoveLoop( struct Node* list)
{
struct Node *slow_p = list, *fast_p = list;

while (slow_p && fast_p && fast_p->next) {
slow_p = slow_p->next;
fast_p = fast_p->next->next;

/* If slow_p and fast_p meet at some point then there
is a loop */
if (slow_p == fast_p) {
removeLoop(slow_p, list);

/* Return 1 to indicate that loop is found */
return 1;
}
}

/* Return 0 to indeciate that ther is no loop*/
return 0;
}

/* Function to remove loop.
loop_node --> Pointer to one of the loop nodes
head -->  Pointer to the start node of the linked list */
void removeLoop( struct Node* loop_node, struct Node* head)
{
struct Node* ptr1;
struct Node* ptr2;

/* Set a pointer to the beginning of the Linked List and
move it one by one to find the first node which is
part of the Linked List */
while (1) {
/* Now start a pointer from loop_node and check if it ever
reaches ptr2 */
ptr2 = loop_node;
while (ptr2->next != loop_node && ptr2->next != ptr1)
ptr2 = ptr2->next;

/* If ptr2 reahced ptr1 then there is a loop. So break the
loop */
if (ptr2->next == ptr1)
break ;

/* If ptr2 did't reach ptr1 then try the next node after ptr1 */
ptr1 = ptr1->next;
}

/* After the end of loop ptr2 is the last node of the loop. So
make next of ptr2 as NULL */
ptr2->next = NULL;
}

/* Function to print linked list */
void printList( struct Node* node)
{
while (node != NULL) {
cout <<node->data <<" " ;
node = node->next;
}
}

struct Node* newNode( int key)
{
struct Node* temp = new Node();
temp->data = key;
temp->next = NULL;
return temp;
}

//Driver Code
int main()
{

/* Create a loop for testing */

cout <<"Linked List after removing loop" <<endl;

return 0;
}

//This code has been contributed by Striver``````

## C

``````//C program to detect and remove loop in linked list
#include <stdio.h>
#include <stdlib.h>

struct Node {
int data;
struct Node* next;
};

/* Function to remove loop. Used by detectAndRemoveLoop() */
void removeLoop( struct Node*, struct Node*);

/* This function detects and removes loop in the list
If loop was there in the list then it returns 1, otherwise returns 0 */
int detectAndRemoveLoop( struct Node* list)
{
struct Node *slow_p = list, *fast_p = list;

while (slow_p && fast_p && fast_p->next) {
slow_p = slow_p->next;
fast_p = fast_p->next->next;

/* If slow_p and fast_p meet at some point then there
is a loop */
if (slow_p == fast_p) {
removeLoop(slow_p, list);

/* Return 1 to indicate that loop is found */
return 1;
}
}

/* Return 0 to indeciate that ther is no loop*/
return 0;
}

/* Function to remove loop.
loop_node --> Pointer to one of the loop nodes
head -->  Pointer to the start node of the linked list */
void removeLoop( struct Node* loop_node, struct Node* head)
{
struct Node* ptr1;
struct Node* ptr2;

/* Set a pointer to the beginning of the Linked List and
move it one by one to find the first node which is
part of the Linked List */
while (1) {
/* Now start a pointer from loop_node and check if it ever
reaches ptr2 */
ptr2 = loop_node;
while (ptr2->next != loop_node && ptr2->next != ptr1)
ptr2 = ptr2->next;

/* If ptr2 reahced ptr1 then there is a loop. So break the
loop */
if (ptr2->next == ptr1)
break ;

/* If ptr2 did't reach ptr1 then try the next node after ptr1 */
ptr1 = ptr1->next;
}

/* After the end of loop ptr2 is the last node of the loop. So
make next of ptr2 as NULL */
ptr2->next = NULL;
}

/* Function to print linked list */
void printList( struct Node* node)
{
while (node != NULL) {
printf ( "%d  " , node->data);
node = node->next;
}
}

struct Node* newNode( int key)
{
struct Node* temp = ( struct Node*) malloc ( sizeof ( struct Node));
temp->data = key;
temp->next = NULL;
return temp;
}

/* Drier program to test above function*/
int main()
{

/* Create a loop for testing */

printf ( "Linked List after removing loop \n" );
return 0;
}``````

## Java

``````//Java program to detect and remove loop in linked list

static class Node {

int data;
Node next;

Node( int d)
{
data = d;
next = null ;
}
}

//Function that detects loop in the list
int detectAndRemoveLoop(Node node)
{
Node slow = node, fast = node;
while (slow != null && fast != null && fast.next != null ) {
slow = slow.next;
fast = fast.next.next;

//If slow and fast meet at same point then loop is present
if (slow == fast) {
removeLoop(slow, node);
return 1 ;
}
}
return 0 ;
}

//Function to remove loop
void removeLoop(Node loop, Node curr)
{
Node ptr1 = null , ptr2 = null ;

/* Set a pointer to the beginning of the Linked List and
move it one by one to find the first node which is
part of the Linked List */
ptr1 = curr;
while ( 1 == 1 ) {

/* Now start a pointer from loop_node and check if it ever
reaches ptr2 */
ptr2 = loop;
while (ptr2.next != loop && ptr2.next != ptr1) {
ptr2 = ptr2.next;
}

/* If ptr2 reahced ptr1 then there is a loop. So break the
loop */
if (ptr2.next == ptr1) {
break ;
}

/* If ptr2 did't reach ptr1 then try the next node after ptr1 */
ptr1 = ptr1.next;
}

/* After the end of loop ptr2 is the last node of the loop. So
make next of ptr2 as NULL */
ptr2.next = null ;
}

//Function to print the linked list
void printList(Node node)
{
while (node != null ) {
System.out.print(node.data + " " );
node = node.next;
}
}

//Driver program to test above functions
public static void main(String[] args)
{
list.head = new Node( 50 );
list.head.next = new Node( 20 );
list.head.next.next = new Node( 15 );
list.head.next.next.next = new Node( 4 );
list.head.next.next.next.next = new Node( 10 );

//Creating a loop for testing
System.out.println( "Linked List after removing loop : " );
}
}

//This code has been contributed by Mayank Jaiswal``````

## python

``````# Python program to detect and remove loop in linked list

# Node class
class Node:

# Constructor to initialize the node object
def __init__( self , data):
self .data = data
self . next = None

def __init__( self ):

def detectAndRemoveLoop( self ):
slow_p = fast_p = self .head
while (slow_p and fast_p and fast_p. next ):
slow_p = slow_p. next
fast_p = fast_p. next . next

# If slow_p and fast_p meet at some poin
# then there is a loop
if slow_p = = fast_p:
self .removeLoop(slow_p)

# Return 1 to indicate that loop if found
return 1

# Return 0 to indicate that there is no loop
return 0

# Function to remove loop
# loop node-> Pointer to one of the loop nodes
# head --> Pointer to the start node of the
def removeLoop( self , loop_node):

# Set a pointer to the beginning of the linked
# list and move it one by one to find the first
# node which is part of the linked list
while ( 1 ):
# Now start a pointer from loop_node and check
# if it ever reaches ptr2
ptr2 = loop_node
while (ptr2. next ! = loop_node and ptr2. next ! = ptr1):
ptr2 = ptr2. next

# If ptr2 reached ptr1 then there is a loop.
# So break the loop
if ptr2. next = = ptr1 :
break

ptr1 = ptr1. next

# After the end of loop ptr2 is the lsat node of
# the loop. So make next of ptr2 as NULL
ptr2. next = None
# Function to insert a new node at the beginning
def push( self , new_data):
new_node = Node(new_data)

def printList( self ):
while (temp):
print temp.data, temp = temp. next

# Driver program
llist.push( 10 )
llist.push( 4 )
llist.push( 15 )
llist.push( 20 )
llist.push( 50 )

# Create a loop for testing
llist.head. next . next . next . next . next = llist.head. next . next

llist.detectAndRemoveLoop()

print "Linked List after removing loop"
llist.printList()

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)``````

## C#

``````//C# program to detect and remove loop in linked list
using System;

public class Node {

public int data;
public Node next;

public Node( int d)
{
data = d;
next = null ;
}
}

//Function that detects loop in the list
int detectAndRemoveLoop(Node node)
{
Node slow = node, fast = node;
while (slow != null && fast != null && fast.next != null ) {
slow = slow.next;
fast = fast.next.next;

//If slow and fast meet at same point then loop is present
if (slow == fast) {
removeLoop(slow, node);
return 1;
}
}
return 0;
}

//Function to remove loop
void removeLoop(Node loop, Node curr)
{
Node ptr1 = null , ptr2 = null ;

/* Set a pointer to the beginning of the Linked List and
move it one by one to find the first node which is
part of the Linked List */
ptr1 = curr;
while (1 == 1) {

/* Now start a pointer from loop_node and check if it ever
reaches ptr2 */
ptr2 = loop;
while (ptr2.next != loop && ptr2.next != ptr1) {
ptr2 = ptr2.next;
}

/* If ptr2 reahced ptr1 then there is a loop. So break the
loop */
if (ptr2.next == ptr1) {
break ;
}

/* If ptr2 did't reach ptr1 then try the next node after ptr1 */
ptr1 = ptr1.next;
}

/* After the end of loop ptr2 is the last node of the loop. So
make next of ptr2 as NULL */
ptr2.next = null ;
}

//Function to print the linked list
void printList(Node node)
{
while (node != null ) {
Console.Write(node.data + " " );
node = node.next;
}
}

//Driver program to test above functions
public static void Main(String[] args)
{

//Creating a loop for testing
Console.WriteLine( "Linked List after removing loop : " );
}
}

//This code has been contributed by 29AjayKumar``````

``````Linked List after removing loop
50 20 15 4 10``````

1. 此方法还取决于Floyd的循环检测算法。
2. 使用弗洛伊德(Floyd)的循环检测算法检测循环, 并获得指向循环节点的指针。
3. 计算循环中的节点数。让计数为k。
4. 将一个指针固定到头部, 将另一个指针固定到头部的第k个节点。
5. 以相同的速度移动两个指针, 它们将在循环起始节点相遇。
6. 获取指向循环的最后一个节点的指针, 然后将其作为NULL。

## CPP

``````#include <bits/stdc++.h>
using namespace std;

struct Node {
int data;
struct Node* next;
};

/* Function to remove loop. */
void removeLoop( struct Node*, struct Node*);

/* This function detects and removes loop in the list
If loop was there in the list then it returns 1, otherwise returns 0 */
int detectAndRemoveLoop( struct Node* list)
{
struct Node *slow_p = list, *fast_p = list;

//Iterate and find if loop exists or not
while (slow_p && fast_p && fast_p->next) {
slow_p = slow_p->next;
fast_p = fast_p->next->next;

/* If slow_p and fast_p meet at some point then there
is a loop */
if (slow_p == fast_p) {
removeLoop(slow_p, list);

/* Return 1 to indicate that loop is found */
return 1;
}
}

/* Return 0 to indicate that there is no loop*/
return 0;
}

/* Function to remove loop.
loop_node --> Pointer to one of the loop nodes
head -->  Pointer to the start node of the linked list */
void removeLoop( struct Node* loop_node, struct Node* head)
{
struct Node* ptr1 = loop_node;
struct Node* ptr2 = loop_node;

//Count the number of nodes in loop
unsigned int k = 1, i;
while (ptr1->next != ptr2) {
ptr1 = ptr1->next;
k++;
}

//And the other pointer to k nodes after head
for (i = 0; i <k; i++)
ptr2 = ptr2->next;

/*  Move both pointers at the same pace, they will meet at loop starting node */
while (ptr2 != ptr1) {
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}

//Get pointer to the last node
while (ptr2->next != ptr1)
ptr2 = ptr2->next;

/* Set the next node of the loop ending node
to fix the loop */
ptr2->next = NULL;
}

/* Function to print linked list */
void printList( struct Node* node)
{
//Print the list after loop removal
while (node != NULL) {
cout <<node->data <<" " ;
node = node->next;
}
}

struct Node* newNode( int key)
{
struct Node* temp = new Node();
temp->data = key;
temp->next = NULL;
return temp;
}

//Driver Code
int main()
{

/* Create a loop for testing */

cout <<"Linked List after removing loop \n" ;
return 0;
}

//This code has been contributed by Striver``````

## C

``````#include <bits/stdc++.h>
using namespace std;

struct Node {
int data;
struct Node* next;
};

/* Function to remove loop. */
void removeLoop( struct Node*, struct Node*);

/* This function detects and removes loop in the list
If loop was there in the list then it returns 1, otherwise returns 0 */
int detectAndRemoveLoop( struct Node* list)
{
struct Node *slow_p = list, *fast_p = list;

//Iterate and find if loop exists or not
while (slow_p && fast_p && fast_p->next) {
slow_p = slow_p->next;
fast_p = fast_p->next->next;

/* If slow_p and fast_p meet at some point then there
is a loop */
if (slow_p == fast_p) {
removeLoop(slow_p, list);

/* Return 1 to indicate that loop is found */
return 1;
}
}

/* Return 0 to indicate that there is no loop*/
return 0;
}

/* Function to remove loop.
loop_node --> Pointer to one of the loop nodes
head -->  Pointer to the start node of the linked list */
void removeLoop( struct Node* loop_node, struct Node* head)
{
struct Node* ptr1 = loop_node;
struct Node* ptr2 = loop_node;

//Count the number of nodes in loop
unsigned int k = 1, i;
while (ptr1->next != ptr2) {
ptr1 = ptr1->next;
k++;
}

//And the other pointer to k nodes after head
for (i = 0; i <k; i++)
ptr2 = ptr2->next;

/*  Move both pointers at the same pace, they will meet at loop starting node */
while (ptr2 != ptr1) {
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}

//Get pointer to the last node
while (ptr2->next != ptr1)
ptr2 = ptr2->next;

/* Set the next node of the loop ending node
to fix the loop */
ptr2->next = NULL;
}

/* Function to print linked list */
void printList( struct Node* node)
{
//Print the list after loop removal
while (node != NULL) {
cout <<node->data <<" " ;
node = node->next;
}
}

struct Node* newNode( int key)
{
struct Node* temp = new Node();
temp->data = key;
temp->next = NULL;
return temp;
}

//Driver Code
int main()
{

/* Create a loop for testing */

cout <<"Linked List after removing loop \n" ;
return 0;
}

//This code has been contributed by Striver``````

## Java

``````//Java program to detect and remove loop in linked list

static class Node {

int data;
Node next;

Node( int d)
{
data = d;
next = null ;
}
}

//Function that detects loop in the list
int detectAndRemoveLoop(Node node)
{
Node slow = node, fast = node;
while (slow != null && fast != null && fast.next != null ) {
slow = slow.next;
fast = fast.next.next;

//If slow and fast meet at same point then loop is present
if (slow == fast) {
removeLoop(slow, node);
return 1 ;
}
}
return 0 ;
}

//Function to remove loop
{
Node ptr1 = loop;
Node ptr2 = loop;

//Count the number of nodes in loop
int k = 1 , i;
while (ptr1.next != ptr2) {
ptr1 = ptr1.next;
k++;
}

//And the other pointer to k nodes after head
for (i = 0 ; i <k; i++) {
ptr2 = ptr2.next;
}

/*  Move both pointers at the same pace, they will meet at loop starting node */
while (ptr2 != ptr1) {
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}

//Get pointer to the last node
while (ptr2.next != ptr1) {
ptr2 = ptr2.next;
}

/* Set the next node of the loop ending node
to fix the loop */
ptr2.next = null ;
}

//Function to print the linked list
void printList(Node node)
{
while (node != null ) {
System.out.print(node.data + " " );
node = node.next;
}
}

//Driver program to test above functions
public static void main(String[] args)
{
list.head = new Node( 50 );
list.head.next = new Node( 20 );
list.head.next.next = new Node( 15 );
list.head.next.next.next = new Node( 4 );
list.head.next.next.next.next = new Node( 10 );

//Creating a loop for testing
System.out.println( "Linked List after removing loop : " );
}
}

//This code has been contributed by Mayank Jaiswal``````

## python

``````# Python program to detect and remove loop in linked list

# Node class
class Node:

# Constructor to initialize the node object
def __init__( self , data):
self .data = data
self . next = None

def __init__( self ):

def detectAndRemoveLoop( self ):
slow_p = fast_p = self .head

while (slow_p and fast_p and fast_p. next ):
slow_p = slow_p. next
fast_p = fast_p. next . next

# If slow_p and fast_p meet at some point then
# there is a loop
if slow_p = = fast_p:
self .removeLoop(slow_p)

# Return 1 to indicate that loop is found
return 1

# Return 0 to indicate that there is no loop
return 0

# Function to remove loop
# loop_node --> pointer to one of the loop nodes
# head --> Pointer to the start node of the linked list
def removeLoop( self , loop_node):
ptr1 = loop_node
ptr2 = loop_node

# Count the number of nodes in loop
k = 1
while (ptr1. next ! = ptr2):
ptr1 = ptr1. next
k + = 1

# Fix one pointer to head

# And the other pointer to k nodes after head
for i in range (k):
ptr2 = ptr2. next

# Move both pointers at the same place
# they will meet at loop starting node
while (ptr2 ! = ptr1):
ptr1 = ptr1. next
ptr2 = ptr2. next

# Get pointer to the last node
while (ptr2. next ! = ptr1):
ptr2 = ptr2. next

# Set the next node of the loop ending node
# to fix the loop
ptr2. next = None

# Function to insert a new node at the beginning
def push( self , new_data):
new_node = Node(new_data)

def printList( self ):
while (temp):
print temp.data, temp = temp. next

# Driver program
llist.push( 10 )
llist.push( 4 )
llist.push( 15 )
llist.push( 20 )
llist.push( 50 )

# Create a loop for testing
llist.head. next . next . next . next . next = llist.head. next . next

llist.detectAndRemoveLoop()

print "Linked List after removing loop"
llist.printList()

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)``````

## C#

``````//A C# program to detect and remove loop in linked list
using System;

public class Node {

public int data;
public Node next;

public Node( int d)
{
data = d;
next = null ;
}
}

//Function that detects loop in the list
int detectAndRemoveLoop(Node node)
{
Node slow = node, fast = node;
while (slow != null && fast != null && fast.next != null ) {
slow = slow.next;
fast = fast.next.next;

//If slow and fast meet at same
//point then loop is present
if (slow == fast) {
removeLoop(slow, node);
return 1;
}
}
return 0;
}

//Function to remove loop
{
Node ptr1 = loop;
Node ptr2 = loop;

//Count the number of nodes in loop
int k = 1, i;
while (ptr1.next != ptr2) {
ptr1 = ptr1.next;
k++;
}

//And the other pointer to k nodes after head
for (i = 0; i <k; i++) {
ptr2 = ptr2.next;
}

/* Move both pointers at the same pace, they will meet at loop starting node */
while (ptr2 != ptr1) {
ptr1 = ptr1.next;
ptr2 = ptr2.next;
}

//Get pointer to the last node
while (ptr2.next != ptr1) {
ptr2 = ptr2.next;
}

/* Set the next node of the loop ending node
to fix the loop */
ptr2.next = null ;
}

//Function to print the linked list
void printList(Node node)
{
while (node != null ) {
Console.Write(node.data + " " );
node = node.next;
}
}

//Driver program to test above functions
public static void Main(String[] args)
{

//Creating a loop for testing
Console.WriteLine( "Linked List after removing loop : " );
}
}

//This code contributed by Rajput-Ji``````

``````Linked List after removing loop
50 20 15 4 10``````

``````Distance traveled by fast pointer = 2 * (Distance traveled
by slow pointer)

(m + n*x + k) = 2*(m + n*y + k)

Note that before meeting the point shown above, fast
was moving at twice speed.

x -->  Number of complete cyclic rounds made by
fast pointer before they meet first time

y -->  Number of complete cyclic rounds made by
slow pointer before they meet first time``````

``````m + k = (x-2y)*n

Which means m+k is a multiple of n.
Thus we can write, m + k = i*n or m = i*n - k.
Hence, distance moved by slow pointer: m, is equal to distance moved by fast pointer:
i*n - k or (i-1)*n + n - k (cover the loop completely i-1 times and start from n-k).``````

## C++

``````//C++ program to detect and remove loop
#include <bits/stdc++.h>
using namespace std;

struct Node {
int key;
struct Node* next;
};

Node* newNode( int key)
{
Node* temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}

//A utility function to print a linked list
{
}
cout <<endl;
}

//Function to detect and remove loop
//in a linked list that may contain loop
{
//If list is empty or has only one node
//without loop
return ;

//Move slow and fast 1 and 2 steps
slow = slow->next;
fast = fast->next->next;

//Search for loop using slow and
//fast pointers
while (fast && fast->next) {
if (slow == fast)
break ;
slow = slow->next;
fast = fast->next->next;
}

/* If loop exists */
if (slow == fast) {
while (slow->next != fast->next) {
slow = slow->next;
fast = fast->next;
}

/* since fast->next is the looping point */
fast->next = NULL; /* remove loop */
}
}

/* Driver program to test above function*/
int main()
{

/* Create a loop for testing */

printf ( "Linked List after removing loop \n" );

return 0;
}``````

## Java

``````//Java program to detect and remove loop in linked list

static class Node {

int data;
Node next;

Node( int d)
{
data = d;
next = null ;
}
}

//Function that detects loop in the list
void detectAndRemoveLoop(Node node)
{

//If list is empty or has only one node
//without loop
if (node == null || node.next == null )
return ;

Node slow = node, fast = node;

//Move slow and fast 1 and 2 steps
slow = slow.next;
fast = fast.next.next;

//Search for loop using slow and fast pointers
while (fast != null && fast.next != null ) {
if (slow == fast)
break ;

slow = slow.next;
fast = fast.next.next;
}

/* If loop exists */
if (slow == fast) {
slow = node;
while (slow.next != fast.next) {
slow = slow.next;
fast = fast.next;
}

/* since fast->next is the looping point */
fast.next = null ; /* remove loop */
}
}

//Function to print the linked list
void printList(Node node)
{
while (node != null ) {
System.out.print(node.data + " " );
node = node.next;
}
}

//Driver program to test above functions
public static void main(String[] args)
{
list.head = new Node( 50 );
list.head.next = new Node( 20 );
list.head.next.next = new Node( 15 );
list.head.next.next.next = new Node( 4 );
list.head.next.next.next.next = new Node( 10 );

//Creating a loop for testing
System.out.println( "Linked List after removing loop : " );
}
}

//This code has been contributed by Mayank Jaiswal``````

## python

``````# Python program to detect and remove loop

# Node class
class Node:

# Constructor to initialize the node object
def __init__( self , data):
self .data = data
self . next = None

def __init__( self ):

# Function to insert a new node at the beginning
def push( self , new_data):
new_node = Node(new_data)

def detectAndRemoveLoop( self ):

if self .head is None :
return
if self .head. next is None :
return

# Move slow and fast 1 and 2 steps respectively
slow = slow. next
fast = fast. next . next

# Search for loop using slow and fast pointers
while (fast is not None ):
if fast. next is None :
break
if slow = = fast :
break
slow = slow. next
fast = fast. next . next

# if loop exists
if slow = = fast :
while (slow. next ! = fast. next ):
slow = slow. next
fast = fast. next

# Sinc fast.next is the looping point
fast. next = None # Remove loop

def printList( self ):
while (temp):
print temp.data, temp = temp. next

# Driver program
llist.head. next = Node( 20 )
llist.head. next . next = Node( 15 )
llist.head. next . next . next = Node( 4 )
llist.head. next . next . next . next = Node( 10 )

# Create a loop for testing
llist.head. next . next . next . next . next = llist.head. next . next

llist.detectAndRemoveLoop()

print "Linked List after removing loop"
llist.printList()

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)``````

## C#

``````//C# program to detect and remove loop in linked list
using System;

public class Node {

public int data;
public Node next;

public Node( int d)
{
data = d;
next = null ;
}
}

//Function that detects loop in the list
void detectAndRemoveLoop(Node node)
{

//If list is empty or has only one node
//without loop
if (node == null || node.next == null )
return ;

Node slow = node, fast = node;

//Move slow and fast 1 and 2 steps
slow = slow.next;
fast = fast.next.next;

//Search for loop using slow and fast pointers
while (fast != null && fast.next != null ) {
if (slow == fast)
break ;

slow = slow.next;
fast = fast.next.next;
}

/* If loop exists */
if (slow == fast) {
slow = node;
while (slow.next != fast.next) {
slow = slow.next;
fast = fast.next;
}

/* since fast->next is the looping point */
fast.next = null ; /* remove loop */
}
}

//Function to print the linked list
void printList(Node node)
{
while (node != null ) {
Console.Write(node.data + " " );
node = node.next;
}
}

//Driver program to test above functions
public static void Main(String[] args)
{

//Creating a loop for testing
Console.WriteLine( "Linked List after removing loop : " );
}
}

//This code contributed by Rajput-Ji``````

``````Linked List after removing loop
50 20 15 4 10``````

## C++

``````//C++ program to detect and remove loop
#include <bits/stdc++.h>
using namespace std;

struct Node {
int key;
struct Node* next;
};

Node* newNode( int key)
{
Node* temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}

//A utility function to print a linked list
{
}
cout <<endl;
}

//Function to detect and remove loop
//in a linked list that may contain loop
{
unordered_map<Node*, int> node_map;
//pointer to last node
Node* last = NULL;
//if node not present in the map, insert it in the map
}
//if present, it is a cycle, make the last node's next pointer NULL
else {
last->next = NULL;
break ;
}
}
}
/* Driver program to test above function*/
int main()
{

/* Create a loop for testing */

printf ( "Linked List after removing loop \n" );

return 0;
}``````

## Java

``````//Java program to detect  and remove loop in a linked list
import java.util.*;

static class Node {
int data;
Node next;
Node( int d)
{
data = d;
next = null ;
}
}

/* Inserts a new Node at front of the list. */
static public void push( int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);

/* 3. Make next of new Node as head */

/* 4. Move the head to point to new Node */
}

//Function to print the linked list
void printList(Node node)
{
while (node != null ) {
System.out.print(node.data + " " );
node = node.next;
}
}

//Returns true if the loop is removed from the linked
//list else returns false.
static boolean removeLoop(Node h)
{
HashSet<Node> s = new HashSet<Node>();
Node prev = null ;
while (h != null ) {
//If we have already has this node
//in hashmap it means their is a cycle and we
//need to remove this cycle so set the next of
//the previous pointer with null.

if (s.contains(h)) {
prev.next = null ;
return true ;
}

//If we are seeing the node for
//the first time, insert it in hash
else {
prev = h;
h = h.next;
}
}

return false ;
}

/* Driver program to test above function */
public static void main(String[] args)
{

llist.push( 20 );
llist.push( 4 );
llist.push( 15 );
llist.push( 10 );

/*Create loop for testing */

System.out.println( "Linked List after removing loop" );
}
else
System.out.println( "No Loop found" );
}
}

//This code is contributed by Animesh Nag.`````` 