【解答】2.6 循環する連結リストが与えられたとき、循環する最初のノードを返すアルゴリズムを実装してください。

TestLinkedList.java

import java.util.*;
import org.junit.*;
import static org.junit.Assert.*;

// 定義
// 循環を含む連結リスト: 連結リストAではループを作るために、リスト内のノードの次へのポインタが以前に出現したノードを指している。
//
// 例
// 入力: A->B->C->D->E->C(最初のCと同じもの)
// 出力: C

public class TestLinkedList {
  @Test
  public void testFindFirstNodeOfLoop() {
    // head->6->7->2->3->7(the third node)
    LinkedList<String> list = new LinkedList<String>();
    list.addLast("6");
    list.addLast("7");
    LinkedList.Node<String> firstNodeOfLoop = list.getFirst().next;
    list.addLast("2");
    list.addLast("3");
    list.getLast().next = firstNodeOfLoop;

    LinkedList.Node<String> result = LoopDetector.findFirstNodeOfLoop(list);
    assertEquals("7", result.data);
  }

  @Test
  public void testFindFirstNodeOfLoop2() {
    // head->6->7->2->3->tail
    LinkedList<String> list = new LinkedList<String>();
    list.addLast("6");
    list.addLast("7");
    list.addLast("2");
    list.addLast("3");

    LinkedList.Node<String> result = LoopDetector.findFirstNodeOfLoop(list);
    assertNull(result.data);
  }

  @Test
  public void testFindFirstNodeOfLoop3() {
    // head->6->7->2->3->6(the second node)
    LinkedList<String> list = new LinkedList<String>();
    list.addLast("6");
    list.addLast("7");
    list.addLast("2");
    list.addLast("3");
    LinkedList.Node<String> firstNodeOfLoop = list.getFirst();
    list.getLast().next = firstNodeOfLoop;

    LinkedList.Node<String> result = LoopDetector.findFirstNodeOfLoop(list);
    assertEquals("6", result.data);
  }
}

class LoopDetector {
  public static HashMap<LinkedList.Node<String>, Boolean> nodeMap = new HashMap<LinkedList.Node<String>, Boolean>();
  public static LinkedList.Node<String> findFirstNodeOfLoop(LinkedList<String> list){
    if(hasLoop(list)){
      LinkedList.Node<String> slowRunner = list.getFirst();
      LinkedList.Node<String> fastRunner = list.getFirst();
      LinkedList.Node<String> countRunner = list.getFirst();
      while(true){
        slowRunner = slowRunner.next;
        fastRunner = fastRunner.next.next;
        if(slowRunner == fastRunner){
          break;
        }
      }
      while(slowRunner != countRunner){
        slowRunner = slowRunner.next;
        countRunner = countRunner.next;
      }
      return countRunner;
    } else {
      return new LinkedList.Node<String>();
    }
  }

  public static boolean hasLoop(LinkedList<String> list){
    LinkedList.Node<String> slow = list.getFirst();
    LinkedList.Node<String> fast = list.getFirst();

    while(slow.data != null && fast.data != null){
      slow = slow.next;
      fast = fast.next.next;
      if(slow == fast){
        return true;
      }
    }
    return false;
  }
}

class LinkedList<E> {
  static class Node<E>{
    public E data;
    public Node<E> next = null;

    public String printNodesToLast(){
      Node<E> node = this;
      StringBuilder sb = new StringBuilder();
      while(node.next != null){
        sb.append(node.data);
        sb.append("->");
        node = node.next;
      }
      int len = sb.length();
      sb.delete(len - 2, len);
      return sb.toString();
    }
  }

  Node<E> head;
  Node<E> tail;

  public LinkedList(){
    this.head = new Node<E>();
    this.tail = new Node<E>();
    head.next = tail;
  }

  public void addLast(E e){
    Node<E> node = new Node<E>();
    this.tail.data = e;
    tail.next = node;
    this.tail = node;
  }

  public void addFirst(E e){
    Node<E> node = new Node<E>();
    node.data = e;
    Node<E> first = this.head.next;
    this.head.next = node;
    node.next = first;
  }

  public Node<E> getFirst(){
    if(this.head.next == tail) return null;
    return this.head.next;
  }

  public Node<E> getLast(){
    Node<E> node = this.head.next;
    Node<E> last = node;
    if(node == this.tail){
      return null;
    }
    while(node != this.tail){
      last = node;
      node = node.next;
    }
    return last;
  }

  public int length(){
    Node<E> node = this.head.next;
    int length = 0;
    while(node.next != null){
      length++;
      node = node.next;
    }
    return length;
  }
}