本文概述
- C ++
- Java
文章图片
方法:在这篇文章中, 我们将使用Map存储存在的节点的地址链表作为键, 其位置作为值。
以下是分步方法:
- 遍历链表的每个节点, 并保持位置从一个开始。在每个节点之后增加位置。
- 检查Map中是否存在该节点。
- 如果Map不包含该节点的地址, 则将其及其位置插入Map。
- 如果Map已经包含该节点的地址, 则返回其位置之间的差。
- 如果找不到这样的节点, 则返回0。
C ++
//C++ program to find length of loop
//in a linked list using Map
#include <
bits/stdc++.h>
using namespace std;
//Linked List node
struct Node {
int data;
struct Node* next;
Node( int num)
{
data = https://www.lsbin.com/num;
next = NULL;
}
};
//Function detects and counts loop
//nodes in the list. If loop is not there, //then returns 0
int countNodesinLoop( struct Node* head)
{
struct Node* p = head;
int pos = 0;
//Maintain a map to store addresses
//of node and their position
unordered_map<
Node*, int>
m;
//Traverse through the linked list
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
【算法题(使用Map查找链表中的循环长度)】);
}
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);
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
head->
next->
next->
next->
next->
next = head->
next;
//Call the function for the above linked list
cout <
<
countNodesinLoop(head) <
<
endl;
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 = https://www.lsbin.com/num;
next = null ;
}
}//Function detects and counts loop
//nodes in the list. If loop is not there, //then returns 0
public static int countNodesinLoop(Node head)
{
Node p = head;
int pos = 0 ;
//Maintain a map to store addresses
//of node and their position
HashMap<
Node, Integer>
m = new HashMap<
Node, Integer>
();
//Traverse through the linked list
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
head.next.next.next.next.next = head.next;
//Call the function for the above linked list
System.out.println(countNodesinLoop(head));
}
}
//This code is contributed by adityapande88
输出如下
4
类似文章:
使用弗洛伊德(Floyd)的循环检测算法在"链表"中查找循环的长度
推荐阅读
- 在Python中查找字符串中每个单词的频率
- UNIX中的绝对和相对路径名简要介绍
- 高级数据结构(二项堆实现原理详细介绍)
- Python –两个变量之间的Pearson相关检验
- GCC和G++之间有什么区别()
- 朴素的模式搜索算法详细介绍
- 8051微控制器的引脚图详细介绍
- Java程序常见问题分析|S14(构造函数)
- 如何在Python 3中使用列表作为字典的键()