【解答1】2.7 連結リストが回文(先頭から巡回しても末尾から巡回しても、各ノードの要素がまったく同じになっている)かどうかを調べる関数を実装してください。

TestLinkedList.java

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

public class TestLinkedList {
  @Test
  public void testPalindromeDetector(){
    LinkedList<Integer> list = new LinkedList<Integer>();
    list.addFirst(1);
    list.addFirst(2);
    list.addFirst(3);
    list.addFirst(2);
    list.addFirst(1);

    boolean isPalindrome = PalindromeDetector.detectPalindrome(list);
    assertTrue(isPalindrome);
  }

  @Test
  public void testPalindromeDetector2(){
    LinkedList<Integer> list = new LinkedList<Integer>();
    list.addFirst(1);
    list.addFirst(1);

    boolean isPalindrome = PalindromeDetector.detectPalindrome(list);
    assertTrue(isPalindrome);
  }

  @Test
  public void testPalindromeDetector3(){
    LinkedList<Integer> list = new LinkedList<Integer>();
    list.addFirst(1);
    list.addFirst(2);
    list.addFirst(1);

    boolean isPalindrome = PalindromeDetector.detectPalindrome(list);
    assertTrue(isPalindrome);
  }

  @Test
  public void testPalindromeDetector4(){
    LinkedList<Integer> list = new LinkedList<Integer>();
    list.addFirst(1);
    list.addFirst(2);
    list.addFirst(2);
    list.addFirst(1);

    boolean isPalindrome = PalindromeDetector.detectPalindrome(list);
    assertTrue(isPalindrome);
  }

  @Test
  public void testPalindromeDetector5(){
    LinkedList<Integer> list = new LinkedList<Integer>();
    list.addFirst(1);
    list.addFirst(2);
    list.addFirst(3);
    list.addFirst(3);
    list.addFirst(1);

    boolean isPalindrome = PalindromeDetector.detectPalindrome(list);
    assertFalse(isPalindrome);
  }

  @Test
  public void testPalindromeDetector6(){
    LinkedList<Integer> list = new LinkedList<Integer>();
    list.addFirst(1);
    list.addFirst(2);

    boolean isPalindrome = PalindromeDetector.detectPalindrome(list);
    assertFalse(isPalindrome);
  }

  @Test
  public void testPalindromeDetector7(){
    LinkedList<Integer> list = new LinkedList<Integer>();
    list.addFirst(1);

    boolean isPalindrome = PalindromeDetector.detectPalindrome(list);
    assertFalse(isPalindrome);
  }

  @Test
  public void testPalindromeDetector8(){
    LinkedList<Integer> list = new LinkedList<Integer>();

    boolean isPalindrome = PalindromeDetector.detectPalindrome(list);
    assertFalse(isPalindrome);
  }
}

class PalindromeDetector {
  public static boolean detectPalindrome(LinkedList<Integer> list){
    if(list.length() <= 1){
      return false;
    }

    Stack<Integer> stack = new Stack<Integer>();
    LinkedList.Node<Integer> slow = list.getFirst();
    LinkedList.Node<Integer> fast = list.getFirst();
    stack.push(slow.data);
    while(fast != list.tail && fast.next != list.tail){
      slow = slow.next;
      fast = fast.next.next;
      if(fast == list.tail){
        break;
      }
      stack.push(slow.data);
    }

    while(slow != list.tail){
      if(stack.pop() != slow.data){
        return false;
      }
      slow = slow.next;
    }
    return true;
  }
}

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;
  }
}