Detectando o início de um Loop em uma lista encadeada (em Java)

Eventualmente, é bom revisitar alguns temas clássicos de ciências da computação. Nesse post, vamos ver como detectar o nodo de início de um Loop em uma lista encadeada.

Dessa vez, estaremos usando Java. Entretanto, o código em C# seria bastante parecido.

O que é uma lista encadeada?

Pegando a definição da wikipedia:

Uma lista ligada ou lista encadeada é uma estrutura de dados linear e dinâmica. Ela é composta por células que apontam para o próximo elemento da lista. Para “ter” uma lista ligada/encadeada, basta guardar seu primeiro elemento, e seu último elemento aponta para uma célula nula.

Definindo um Nodo

O primeiro passo para definir uma Lista Encadeada é definir um Nodo. Eis uma implementação simples:

package com.elemarjr.LinkedListsXp;

public class Node<T> {
	
	private T data;
	private Node<T> next;
	
	public Node() {}
	
	public Node(T data)
	{
		this();
		this.data = data;
	}
	
	public T getData() { return data; }
	public void setData(T value) { data = value; }
	
	public Node<T> getNext() { return next; }
	public void setNext(Node<T> value) { next = value; }
}

Aqui, nada de especial. Temos data armazenando o valor correspondente ao nodo e next apontando para o próximo nodo da lista.

Alguns testes:

package com.elemarjr.LinkedListsXp.Tests;

import com.elemarjr.LinkedListsXp.*;
import static org.junit.Assert.*;

import org.junit.Test;

public class NodeTests {

	@Test
	public void nodeStoresDataPassedWithCtor() {
		Node<String> node = new Node<>("abc");
		assertEquals(node.getData(), "abc");
	}
	
	@Test
	public void nodeStoresNext() {
		Node<String> node1 = new Node<>("abc");
		Node<String> node2 = new Node<>("def");
		
		node1.setNext(node2);
		assertEquals(node1.getNext(), node2);
	}
	
	@Test
	public void nodeStoresData() {
		Node<String> node = new Node<>();
		node.setData("abc");
		assertEquals(node.getData(), "abc");
	}
}

Implementando a lista

A lista consiste basicamente de uma referência para o primeiro nodo da lista. Interessante, mesmo é a implementação do método que verifica se a lista é circular e do outro que encontra o primeiro elemento.

package com.elemarjr.LinkedListsXp;

import java.util.List;

public class LinkedList<T> {
	
	Node<T> head;
	
	public LinkedList(Node<T> head) {
		this.head = head;
	}
	
	public LinkedList(List<T> elements) {
		Node<T> previous = null;
		for (T element: elements) {
			Node<T> node = new Node<>(element);
			if (previous != null) {
				previous.setNext(node);
			} else {
				head = node;
			}
			previous = node;
		}
	}
	
	public Node<T> getHead() { 
		return head;
	}
	
	public void setHead(Node<T> value) {
		head = value;
	}
	
	public boolean isCircular() {
		Node<T> slow = head;
		Node<T> fast = head;
		while (fast != null && fast.getNext() != null) {
			slow = slow.getNext();
			fast = fast.getNext().getNext();
			if (slow == fast) return true;
		}
		return false;
	}
	
	public Node<T> firstNodeOfCircularLoop() {
		Node<T> slow = head, fast = head;
		
		while (fast != null && fast.getNext() != null) {
			slow = slow.getNext();
			fast = fast.getNext().getNext();
			if (slow == fast) break;
		}
		
		if (fast == null || fast.getNext() == null) 
		{
			return null;
		}
		
		slow = head;
		while (slow != fast)
		{
			slow = slow.getNext();
			fast = fast.getNext();
		}
		
		return slow;
	}
}

Defini dois construtores Um que aceita uma referência para o Nodo “head” e outro que aceita uma lista que será convertida para lista ligada.

O método que verifica se a lista é circular inicia dois cursores. Um que vale a lista avançando um elemento por vez, e outro que avança dois elementos. Se, em algum momento, ambos os cursores apontarem para o mesmo nodo, então, teremos uma lista circular. Perceba que não há chances do cursor rápido simplesmente pular o cursor lento.

Eis os testes:

package com.elemarjr.LinkedListsXp.Tests;

import com.elemarjr.LinkedListsXp.*;

import java.util.Arrays;

import org.junit.Test;
import static org.junit.Assert.*;

public class LinkedListTests {

	@Test
	public void createLinkedListFromList() {
		Integer[] values = new Integer[] {1, 2, 3, 4, 5};
		LinkedList<Integer> list = new LinkedList<>(Arrays.asList(values));
		
		Node<Integer> head = list.getHead();
		int index = 0;
		
		while (head != null) {
			assertEquals(head.getData(),values[index]);
			index++;
			head = head.getNext();
		}
	}
	
	@Test
	public void isCircularReturnsFalseWhenListIsNotCircular() {
		Integer[] values = new Integer[] {1, 2, 3, 4, 5};
		LinkedList<Integer> list = new LinkedList<>(Arrays.asList(values));
		assertFalse(list.isCircular());
	}
	
	@Test
	public void isCircularReturnsTrueWhenListIsCircular() {
		Node<Integer> one = new Node<>(1);
		Node<Integer> two = new Node<>(2);
		one.setNext(two);
		Node<Integer> three = new Node<>(3);
		two.setNext(three);
		Node<Integer> four = new Node<>(4);
		three.setNext(four);
		Node<Integer> five = new Node<>(5);
		four.setNext(five);
		five.setNext(three);
		
		LinkedList<Integer> list = new LinkedList<>(one);
		assertTrue(list.isCircular());
	}
	
	@Test
	public void firstNodeOfCircularLoopReturnsCorrectNode() {
		Node<Integer> one = new Node<>(1);
		Node<Integer> two = new Node<>(2);
		one.setNext(two);
		Node<Integer> three = new Node<>(3);
		two.setNext(three);
		Node<Integer> four = new Node<>(4);
		three.setNext(four);
		Node<Integer> five = new Node<>(5);
		four.setNext(five);
		five.setNext(three);
		
		LinkedList<Integer> list = new LinkedList<>(one);
		
		assertEquals(three, list.firstNodeOfCircularLoop());
	}
	
	@Test
	public void firstNodeOfCircularLoopReturnsNullWhenListIsNotCircular() {
		Integer[] values = new Integer[] {1, 2, 3, 4, 5};
		LinkedList<Integer> list = new LinkedList<>(Arrays.asList(values));
		assertEquals(null, list.firstNodeOfCircularLoop());
	}
}

Pronto!