专注七星彩网站开发/网站建设报价方案

题目：

请判断一个链表是否为回文链表。

示例 1:
输入: 1->2
输出: false

示例 2:
输入: 1->2->2->1
输出: true

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

思路：

思路: 可以使用快慢指针进行链表遍历。
[1]先构建出一个空节点,让慢指针指向该节点，快指针指向head节点(遍历时,head速度是slow的两倍)
[2]当fast节点为空或者fast节点的下一个节点为空, 则slow刚好走到一半差一个节点
(这样可以不分奇偶数，slow的下一个节点刚好为一半)
[3]使用头插法进行链表的反转
[4] 比较两个链表的值。

代码

/*** 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 dumpy = new ListNode(-1);dumpy.next = head;ListNode slow = dumpy;ListNode fast = head;while(fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;}//使用头插法反转后半截链表ListNode head2 = reverse(slow.next);//让head节点的尾部结上一个空节点slow.next = null;while(head != null && head2 != null) {if(head.val != head2.val) {return false;}head = head.next;head2 = head2.next;}return true;}//使用头插法反转链表private ListNode reverse(ListNode cur) {ListNode head = new ListNode(-1);while(cur != null) {ListNode node = new ListNode(cur.val);node.next = head.next;head.next = node;cur = cur.next;}return head.next;}}