[ 热题 HOT 100] ---234. 回文链表 ---双指针

1 题目描述

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

示例 1:

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

输入: 1->2->2->1 输出: true 进阶： 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/palindrome-linked-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2 解题思路

判断回文链表可以分为三步 （1）找到链表的中点。这一步是通过快慢指针实现的。 （2）反转中点也就是slow目前所在位置的后半部分。 交换的过程可以参照下面这张图片 （3）链表前后进行对比。不同返回false，否则继续往后面比。

返回值：当上面的所有条件都满足的时候，这就是个回文链表了，所以返回true即可。

3 解决代码

/** * 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 || head.next == null) return true; ListNode fast = head; ListNode slow = head; ListNode pre = null; //第一步，快慢指针，找到链表的中点 while(fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; } //第二步，将slow之后的后半部分进行链表反转 while(slow != null){ ListNode next = slow.next; slow.next = pre; pre = slow; slow = next; } //第三步，前后链表进行比较 while(head != null && pre != null){ if(head.val != pre.val){ return false; } head = head.next; pre = pre.next; } return true; } }