【 Java 】 함 수 를 작성 하여 링크 가 답장 인지 확인 합 니 다.

쾌속 포인터 가 링크 의 중간 점 을 찾 았 다.
1. 앞부분 을 뒤 집어 서 뒷부분 과 똑 같은 지 확인
2. 앞부분 을 창고 에 넣 고 나머지 절반 의 결산 점 을 반복 해서 방문 합 니 다. 매번 창고 꼭대기 요 소 는 똑 같이 리 턴 링크 입 니 다.

import java.util.Stack;
public class isHuiWen {
	public boolean isPalinddrome(LinkedListNode head) {
		LinkedListNode fast = head;
		LinkedListNode slow = head;
		
		Stack stack = new Stack();
		
		while( fast != null && fast.next != null ) {
			stack.push(slow.data);
			slow = slow.next;
			fast = fast.next.next;
		}
		
		//          ，  fast     ，             
		if ( fast != null ) {
			slow = slow.next;
		}
		
		while (slow != null) {
			int top = stack.pop().intValue();
			//     ，     
			if (top != slow.data) {
				return false;
			}
			slow= slow.next;
		}
		return true;
	}
}

재 귀적 해법:

class Result{
	public LinkedListNode node;
	public boolean result;
}

Result isPalindromeRecurse(LinkedListNode head, int length) {
	if (head == null || length == 0) {
		return new Result(null, true);
	}
	else if(length == 1) {
		return new Result(head.next,true);
	}
	else if(length == 2) {
		return new Result(head.next.next, head.data == head.next.data);
	}
	Result res = isPalindromeRecurse(head.next, length -2);
	if(!res.result || res.node == null){
		return res;
	}
	else{
		res.result = head.data == res.node.data;
		res.node = res.node.next;
		return res;
	}
}

boolean isPalinddrome(LinkedListNode head) {
	Result p = isPalindromeRecurse(head, listSize(head));
	return p.result;
}