检测链表中的循环 java的5种方法

Bertha 。 2023-09-24 17:44 33阅读 0赞

# 问题：如果是链表，检查链表是否有环。下图显示了带有循环的链表。 #

![在这里插入图片描述][66dfa2ee05de4cb695d4a52bd404c686.png]

# 方法1：使用 Hashing 检测链表中的循环 #

> 这个想法是将节点插入哈希图中，每当遇到哈希图中已经存在的节点时，就返回 true。
> 
>  *  单独遍历列表并将节点地址放入哈希表中。
>  *  在任何时候，如果达到 NULL，则返回 false
>  *  如果当前节点中的下一个指向哈希中先前存储的任何节点，则返回 true。

> 时间复杂度：`O(N)`，循环只需要遍历一次。 辅助空间：`O(1)`。

// Java program to detect loop in a linked list
    
    import java.io.*;
    
    class LinkedList {
        
    	Node head; // head of list
    
    	/* Linked list Node*/
    	class Node {
        
    		int data;
    		Node next;
    		Node(int d)
    		{
        
    			data = d;
    			next = null;
    		}
    	}
    
    	/* Inserts a new Node at front of the list. */
    	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 */
    		new_node.next = head;
    
    		/* 4. Move the head to point to new Node */
    		head = new_node;
    	}
    
    	void detectLoop()
    	{
        
    		Node slow_p = head, fast_p = head;
    		int flag = 0;
    		while (slow_p != null && fast_p != null
    			&& fast_p.next != null) {
        
    			slow_p = slow_p.next;
    			fast_p = fast_p.next.next;
    			if (slow_p == fast_p) {
        
    				flag = 1;
    				break;
    			}
    		}
    		if (flag == 1)
    			System.out.println("Loop Found");
    		else
    			System.out.println("No Loop");
    	}
    
    	/* Driver program to test above functions */
    	public static void main(String args[])
    	{
        
    		LinkedList llist = new LinkedList();
    
    		llist.push(20);
    		llist.push(4);
    		llist.push(15);
    		llist.push(10);
    
    		/*Create loop for testing */
    		llist.head.next.next.next.next = llist.head;
    
    		llist.detectLoop();
    	}
    }

Loop Found

# 方法2：通过标记已访问节点而不修改节点结构来检测链表中的循环 #

> 将链表的当前节点指向创建的节点。每当一个节点的 next 指向该节点时，就意味着循环就在那里。
> 
>  *  创建一个临时节点。 使遍历的每个节点的下一个指针指向这个临时节点。
>  *  这样我们就把节点的 next 指针作为一个标志来表示该节点是否已经遍历。
>  *  检查每个节点以查看下一个节点是否指向临时节点。
>  *  在循环的第一个节点的情况下，我们第二次遍历它时这个条件将为真，因此我们发现循环存在。
>  *  如果我们遇到一个指向 null 的节点，则循环不存在。

> 时间复杂度：`O(N)`。只需要遍历一次循环。 辅助空间：`O(1)`

// Java program to return first node of loop
    public class GFG {
        
    
    	static class Node {
        
    		int key;
    		Node next;
    	};
    
    	static Node newNode(int key)
    	{
        
    		Node temp = new Node();
    		temp.key = key;
    		temp.next = null;
    		return temp;
    	}
    
    	// A utility function to print a linked list
    	static void printList(Node head)
    	{
        
    		while (head != null) {
        
    			System.out.print(head.key + " ");
    			head = head.next;
    		}
    		System.out.println();
    	}
    
    	// Function to detect first node of loop
    	// in a linked list that may contain loop
    	static boolean detectLoop(Node head)
    	{
        
    
    		// Create a temporary node
    		Node temp = new Node();
    		while (head != null) {
        
    
    			// This condition is for the case
    			// when there is no loop
    			if (head.next == null) {
        
    				return false;
    			}
    
    			// Check if next is already
    			// pointing to temp
    			if (head.next == temp) {
        
    				return true;
    			}
    
    			// Store the pointer to the next node
    			// in order to get to it in the next step
    			Node next = head.next;
    
    			// Make next point to temp
    			head.next = temp;
    
    			// Get to the next node in the list
    			head = next;
    		}
    
    		return false;
    	}
    
    	// Driver code
    	public static void main(String args[])
    	{
        
    		Node head = newNode(1);
    		head.next = newNode(2);
    		head.next.next = newNode(3);
    		head.next.next.next = newNode(4);
    		head.next.next.next.next = newNode(5);
    
    		// Create a loop for testing(5 is pointing to 3) /
    		head.next.next.next.next.next = head.next.next;
    
    		boolean found = detectLoop(head);
    		if (found)
    			System.out.println("Loop Found");
    		else
    			System.out.println("No Loop");
    	}
    };

Loop Found

# 方法3：通过存储长度检测链表中的循环 #

> 存储列表从第一个节点到最后一个节点的长度，增加最后一个节点直到达到 NULL 或最后一个节点的数量大于第一个和最后一个节点。
> 
>  *  创建了两个指针，first（始终指向 head）和 last。  
>     每次最后一个指针移动时，计算第一个和最后一个之间的节点数。  
>     检查当前节点数是否 > 先前节点数 如果是，我们继续移动最后一个指针 否则这意味着我们已经到达循环的末尾，因此相应地返回输出。

> 时间复杂度：`O(N2)`，对每一个结点遍历计算该结点从头部算起的长度。 辅助空间：`O(1)`

// Java program to return first node of loop
    import java.util.*;
    class GFG
    {
        
    static class Node
    {
        
    	int key;
    	Node next;
    };
    
    static Node newNode(int key)
    {
        
    	Node temp = new Node();
    	temp.key = key;
    	temp.next = null;
    	return temp;
    }
    
    // A utility function to print a linked list
    static void printList(Node head)
    {
        
    	while (head != null)
    	{
        
    		System.out.print(head.key + " ");
    		head = head.next;
    	}
    	System.out.println();
    }
    
    /*returns distance between first and last node every time
    * last node moves forwards*/
    static int distance(Node first, Node last)
    {
        
    
    	/*counts no of nodes between first and last*/
    	int counter = 0;
    	Node curr;
    	curr = first;
    	while (curr != last)
    	{
        
    		counter += 1;
    		curr = curr.next;
    	}
    	return counter + 1;
    }
    
    // Function to detect first node of loop
    // in a linked list that may contain loop
    static boolean detectLoop(Node head)
    {
        
    
    	// Create a temporary node
    	Node temp = new Node();
    	Node first, last;
    
    	/*first always points to head*/
    	first = head;
    
    	/*last pointer initially points to head*/
    	last = head;
    
    	/*current_length stores no of nodes between current
    	* position of first and last*/
    	int current_length = 0;
    
    	/*current_length stores no of nodes between previous
    	* position of first and last*/
    	int prev_length = -1;
    	while (current_length > prev_length && last != null)
    	{
        
    	
    		// set prev_length to current length then update the
    		// current length
    		prev_length = current_length;
    	
    		// distance is calculated
    		current_length = distance(first, last);
    	
    		// last node points the next node
    		last = last.next;
    	}
    	
    	if (last == null)
    	{
        
    		return false;
    	}
    	else
    	{
        
    		return true;
    	}
    }
    
    /* Driver program to test above function*/
    public static void main(String[] args)
    {
        
    	Node head = newNode(1);
    	head.next = newNode(2);
    	head.next.next = newNode(3);
    	head.next.next.next = newNode(4);
    	head.next.next.next.next = newNode(5);
    
    	/* Create a loop for testing(5 is pointing to 3) */
    	head.next.next.next.next.next = head.next.next;
    	boolean found = detectLoop(head);
    	if (found)
    		System.out.print("Loop Found");
    	else
    		System.out.print("No Loop Found");
    }
    }

Loop Found

# 方法4：通过修改值检测链表中的循环 #

> 修改访问节点的值并检查当前节点值是否等于该值。
> 
>  *  遍历链表并将该节点的值（数据）更改为-1。
>  *  现在，在修改值之前检查节点的值是否已经是-1
>  *  如果是 -1 则返回 TRUE 否则，更改节点的值。 遍历链表直到到达 NULL。

> 时间复杂度：`O(N)` 辅助空间：\`O(1)

// Java program to return first node of loop
    import java.util.*;
    
    class LinkedList {
        
    
    	// Head of list
    	static Node head;
    
    	// Linked list Node
    	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 */
    		new_node.next = head;
    
    		/* 4. Move the head to point to new Node */
    		head = new_node;
    	}
    
    	// Function to detect first node of loop
    	// in a linked list that may contain loop
    	static boolean detectLoop(Node h)
    	{
        
    
    		// If the head is null we will return false
    		if (head == null)
    			return false;
    		else {
        
    
    			// Traversing the linked list
    			// for detecting loop
    			while (head != null) {
        
    
    				// If loop found
    				if (head.data == -1) {
        
    					return true;
    				}
    
    				// Changing the data of visited node to any
    				// value which is outside th given range
    				// here it is supposed the given range is (1
    				// <= Data on Node <= 10^3)
    				else {
        
    					head.data = -1;
    					head = head.next;
    				}
    			}
    
    			// If loop not found return false
    			return false;
    		}
    	}
    
    	// Driver Code
    	public static void main(String[] args)
    	{
        
    		LinkedList llist = new LinkedList();
    
    		llist.push(1);
    		llist.push(2);
    		llist.push(3);
    		llist.push(4);
    		llist.push(5);
    
    		/* Create a loop for testing */
    		llist.head.next.next.next.next.next
    			= llist.head.next.next;
    
    		if (detectLoop(llist.head))
    			System.out.println("Loop Found");
    		else
    			System.out.println("Not Found");
    	}
    }

Loop Found

# 方法5：使用 Floyd 的循环查找算法检测链表中的循环 #

> 该算法用于在链表中查找循环。它使用两个指针，一个指针的移动速度是另一个指针的两倍。速度快的称为快指针，另一种称为慢指针。
> 
>  *  使用两个指针遍历链表。 将一个指针 (slow\_p) 移动一个，将另一个指针 (fast\_p) 移动两个。
>  *  如果这些指针在同一节点相遇，则存在循环。如果指针不相交，则链表没有循环。  
>     时间复杂度：`O(N)`，循环只需要遍历一次。 辅助空间：`O(1)`。

![在这里插入图片描述][daa786443a1c4d12a2c26314e973ecf3.png]

Loop Found

[66dfa2ee05de4cb695d4a52bd404c686.png]: https://img-blog.csdnimg.cn/66dfa2ee05de4cb695d4a52bd404c686.png
[daa786443a1c4d12a2c26314e973ecf3.png]: https://img-blog.csdnimg.cn/daa786443a1c4d12a2c26314e973ecf3.png