题目
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
题解
思路：首先使用快慢指针找到后半段开始的位置，然后将后半段翻转，比较前半段链表和后半段翻转链表的值，这里不需要考虑原链表长度是奇数还是偶数，我们只需要比较两段中较短的那一段长度就可以了。
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/
class Solution {public boolean isPalindrome(ListNode head) {ListNode fast = head;ListNode slow = head;while(fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;}slow = reverse(slow); // 翻转后半部分while(slow != null){if(head.val != slow.val) return false;slow = slow.next;head = head.next;}return true;}private ListNode reverse(ListNode root){ListNode p = root;ListNode t = null;while(p != null){root = root.next;p.next = t;t = p;p = root;}return t;}
}