【解答2】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){
    int length = list.length();
    if(length <= 1){
      return false;
    } else {
      Result r = isPalindrome(list.getFirst(), length);
      return r.result;
    }
  }

  static Result isPalindrome(LinkedList.Node<Integer> node, int length){
    if(length <= 1){
      Result r = new Result();
      if(length == 0){
        r.node = node;
      } else {
        r.node = node.next;
      }
      return r;
    }
    Result r = isPalindrome(node.next, length - 2);
    if(r.node.data != node.data){
      r.result = false;
    }
    r.node = r.node.next;
    return r;
  }
}

class Result {
  public LinkedList.Node<Integer> node;
  public boolean result = 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;
  }
}