博客

方法一：

反转前半部分

	/**
	 * 回文链表
	 * 反转前半部分
	 * 两条链条
	 * @param head
	 * @return
	 */
public boolean isPalindrome (ListNode head) {
	if (head ==null || head.next == null) return true;
	ListNode quick = head;
	ListNode slow = head;
	
	// 快慢指针，快指针每次走两步，慢指针每次走一步
	// slow指向中间节点，quick辅助
	while (quick.next != null && quick.next.next != null) {
		quick = quick.next.next;
		slow = slow.next;
	}
	
	// 判断回文链表奇数还是偶数----通过quick来判断！
	int flag = 1;  //  奇数
	if (quick.next != null) {
		flag = 0;  //  偶数
	}
	
	// 逆置第一段链表
	// 不论是奇数还是偶数，第二段链表的开头都需要指向slow下一个节点
	ListNode head2 = slow.next;
	ListNode cur = head;
	ListNode node = null; //  同逆转链表,设立一个新链表头
	
	// 反转前半部分链表
	// 反转后: 
	// head2--第二段第一个(mark)  
	// node--第一段最后一个--即反转后第一段第一个节点
	// cur--第二段第一个
	while (cur != head2) {
		ListNode next = cur.next;
		cur.next = node;
		node = cur;
		cur = next;
	}
	
	// 如果是奇数12321,跳过3
	// 此时3是前一段链表的表头
	if (flag == 1) {
		node = node.next;
	}
	
	// 统一奇偶数情况之后，开始判断
	// 判定条件，反转后链表和第二段链表
	
	while (head2 != null) {
		if (node.val != head2.val) {
			return false;
		}
		node = node.next;
		head2 = head2.next;
	}
	
	return true;
}

方法二：

反转后半部分：

还没想明白

方法三：

转化为数组

	/**
	 * 回文链表
	 * @param head
	 * @return
	 */
public boolean isPalindrome (ListNode head) {
	// 遍历链表，将值存储到数组中
	ListNode cur = head;
	List<Integer> nums = new ArrayList<>();
	while (cur != null) {
		nums.add(cur.val);
		cur = cur.next;
	}
	// 两个前后指针,检查回文
	int pre = 0;
	int last = nums.size() - 1;
	// 转化为数组，12321和1221可以一起处理
	while (pre < last) {
		// 比较值
		if (!nums.get(pre).equals(nums.get(last))) {
			return false;
		}
		pre++;
		last--;
	}
	
	return true;
}