判断是否是回文链表

package 链表下;

public class palindromeLinkedList {
	/**
	 * 获取链表长度
	 * @param head
	 * @return
	 */
	public static int lengthOfList (ListNode head) {
		ListNode p = head;
		int n = 0;
		while (p != null) {
			p = p.next;
			n++;
		}
		return n;
	}
	
	/**
	 * 链表反转
	 * @param head
	 * @return
	 */
	public static ListNode reverseList (ListNode head) {
		ListNode pre = head;
		ListNode p = pre.next;
		ListNode next;
		while (p != null) {
			next = p.next;
			p.next = pre;
			pre = p;
			p = next;
		}
		head.next = null;
		return pre;
	}
	
	/**
	 * 对链表中轴的右边进行旋转，并双指针进行判断两边是否相等
	 * @param head
	 * @return
	 */
	public static boolean isPalindrome (ListNode head) {
		int n = lengthOfList(head);
		int half = n/2;
		ListNode leftEnd = head;
		for (int i = 0; i < half -1; i++) {
			leftEnd = leftEnd.next;
		}
		ListNode rightStart = leftEnd.next;		//找到右边链表开始的节点
		if (n % 2 != 0) {
			rightStart = rightStart.next;
		}
		rightStart = reverseList(rightStart);   // 逆转右边开始节点的链表
		ListNode leftStart = head;				//左边链表开始的节点
		for (int i = 0; i < half; i++) {
			if (leftStart.val != rightStart.val) {		//左边和右边链表进行比较
				return false;
			}
			leftStart = leftStart.next;
			rightStart = rightStart.next;
		}
		return true;
	}
	
	public static void main(String[] args) {
		int[] array1={1,2,3,4,3,2,1};
		ListNode head=ListNode.arrayToList(array1);
		System.out.println(isPalindrome(head));
		
		int[] array2={1,2,3,4,5,3,2,1};
		ListNode head2=ListNode.arrayToList(array2);
		System.out.println(isPalindrome(head2));
	}
	
}