# 算法题：使用Map查找链表中的循环长度

2021年4月14日14:27:52 发表评论 534 次浏览

## 本文概述

1. 遍历链表的每个节点, 并保持位置从一个开始。在每个节点之后增加位置。
2. 检查Map中是否存在该节点。
3. 如果Map不包含该节点的地址, 则将其及其位置插入Map。
4. 如果Map已经包含该节点的地址, 则返回其位置之间的差。
5. 如果找不到这样的节点, 则返回0。

## C ++

``````//C++ program to find length of loop
//in a linked list using Map

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

struct Node {
int data;
struct Node* next;

Node( int num)
{
data = num;
next = NULL;
}
};

//Function detects and counts loop
//nodes in the list. If loop is not there, //then returns 0
{
int pos = 0;

//Maintain a map to store addresses
//of node and their position
unordered_map<Node*, int> m;

while (p != NULL) {

//If the node is not present in the map
if (m.find(p) == m.end()) {
m = pos;
pos++;
}

//if the node is present
else {

//Return difference between
//position of the present node and
//position where that node occured before
return (pos - m``````);
}
p = p->next;
}

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

//Driver code
int main()
{
//Create nodes of the linked list
struct Node* head = new Node(1);

//Create a loop for testing the function

//Call the function for the above linked list

return 0;
}``````

## Java

``````//Java program to find length of loop
//in a linked list using Map
import java.util.*;
import java.io.*;

class GFG{

static class Node
{
int data;
Node next;

//Constructor
Node( int num)
{
data = num;
next = null ;
}
}

//Function detects and counts loop
//nodes in the list. If loop is not there, //then returns 0
{
int pos = 0 ;

//Maintain a map to store addresses
//of node and their position
HashMap<Node, Integer> m = new HashMap<Node, Integer>();

while (p != null )
{

//If the node is not present in the map
if (!m.containsKey(p))
{
m.put(p, pos);
pos++;
}

//If the node is present
else
{

//Return difference between
//position of the present
//node and position where
//that node occured before
return (pos - m.get(p));
}
p = p.next;
}

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

//Driver code
public static void main (String[] args)
{

//Create nodes of the linked list
Node head = new Node( 1 );
head.next = new Node( 2 );
head.next.next = new Node( 3 );
head.next.next.next = new Node( 4 );
head.next.next.next.next = new Node( 5 );

//Create a loop for testing the function

//Call the function for the above linked list
``4``