中交路桥建设有限公司资质/济源新站seo关键词排名推广

234. 回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

“回文”是指正读反读都能读通的句子，它是古今中外都有的一种修辞方式和文字游戏，如“我为人人，人人为我”等。在数学中也有这样一类数字有这样的特征，成为回文数（palindrome number）。设n是一任意自然数。若将n的各位数字反向排列所得自然数n1与n相等，则称n为回文数。例如，若n=12321或者1221，则称n为回文数；但若n=1234，则n不是回文数。

这里的回文链表也是这个概念，我们需要用O(n)时间复杂度和O(1)空间复杂度解决此题。解题思路也很简单，根据回文数的概念，我们将链表且分为两段，然后把后半段反转，然后比较这两段对位节点是否相等即可。

/*** 234. 回文链表* 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。* https://leetcode-cn.com/problems/palindrome-linked-list/* 简单*/
public class LeetCode234 {public boolean isPalindrome(ListNode head) {//如果是这样，直接返回trueif (head == null || head.next == null) {return true;}/*获取链表中点*/ListNode slow = head;ListNode fast = head.next;//这样也可以//ListNode fast = head.next.next;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;}slow = slow.next;//反转链表，并且断开联系ListNode pre = null;while (slow != null) {ListNode next = slow.next;slow.next = pre;pre = slow;slow = next;}//对比链表节点while (pre != null) {if (pre.val != head.val) {return false;}pre = pre.next;head = head.next;}return true;}public class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) {this.val = val;}ListNode(int val, ListNode next) {this.val = val;this.next = next;}}
}