[LeetCode] 234. Palindrome Linked List

本文主要是介绍[LeetCode] 234. Palindrome Linked List，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题：https://leetcode.com/problems/palindrome-linked-list/description/

题目

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

Follow up:
Could you do it in O(n) time and O(1) space?

题目大意

判断链表是否为回文。

思路

1.用slow ，fast指针找出链表的中间的及结点。

网上有多种方法设置slow、fast与循环的判断条件。

我这里用的是

fast = head
slow = head
while(fast.next != null && fast.next.next !=null)

这样 fast 指向的必有结点。
当链表为奇数结点时，fast停在倒数第一个结点上。slow 在中间结点上。
当链表为偶数时，fast停在倒数第二个结点上。slow在前一半的最后一个结点上。

slow.next 便是后半链表的头结点。

2.截取后半链表翻转。

3.将后翻转的后半链表与原链表逐行对比。遍历中数值不同，返回false。
当后半链表的遍历指针halfHead 或原链表遍历指针 head 为null 跳出循环。

4.若halfHead、head 均为null，两链表相同长度，返回 true。
若head！=null、head.next=null，最初链表为奇数。原链表比后半链表多一个结点，返回true。

否则，返回false。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {if(head == null)return true;ListNode slow = head,fast = head;while(fast.next != null && fast.next.next != null){fast = fast.next.next;slow = slow.next;}//找到中间结点ListNode tTailNode;tTailNode = slow;	//获得后半截链表的头结点。slow = slow.next;//截段后半链表tTailNode.next = null;	//翻转后半链表ListNode halfHead = null;while(slow!=null){ListNode tNode = slow.next;slow.next =halfHead;halfHead = slow;slow = tNode;}	// 两 链表 对比while(head != null && halfHead!=null){if(head.val != halfHead.val)return false;head = head.next;halfHead = halfHead.next;}if((head==null && halfHead==null) ||(head != null && head.next == null))return true;return false;}
}