LeetCode_双指针_简单_234.回文链表

1.题目

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

示例 1： 输入：head = [1,2,2,1] 输出：true

示例 2： 输入：head = [1,2] 输出：false

提示： 链表中节点数目在范围[1, 105] 内 0 <= Node.val <= 9

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/palindrome-linked-list

2.思路

（1）双指针——将值复制到数组中 由于单链表无法倒着遍历，故可以先将链表中的值复制到数组中，然后再使用双指针法判断是否为回文即可。该方法的时间复杂度和空间复杂度均为 O(n)。

（2）双指针

• 通过快慢指针 fast 和 slow 找到链表的中点，可以参考 LeetCode_双指针_简单_876.链表的中间结点这题；
• 从 slow 指针开始反转后面的链表，有关链表反转的具体细节可以参考LeetCode_双指针_递归_简单_206.反转链表这篇文章；
• 最后使用双指针判断回文即可。

相关题目： LeetCode_动态规划_中等_5.最长回文子串 LeetCode_回溯_动态规划_中等_131.分割回文串 LeetCode_贪心算法_简单_409.最长回文串 LeetCode_动态规划_中等_516.最长回文子序列 LeetCode_字符串_中等_647. 回文子串 LeetCode_双指针_简单_1332.删除回文子序列

3.代码实现（Java）

//思路1————双指针——将值复制到数组中 /**
 * Definition for singly-linked list.
 * 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; }
 * }
 */ class Solution { public boolean isPalindrome(ListNode head) { List<Integer> values = new ArrayList<Integer>(); //将链表中的值复制到数组 values 中 ListNode curNode = head; while (curNode != null) { values.add(curNode.val); curNode = curNode.next; } //使用双指针判断回文 int left = 0, right = values.size() - 1; while (left < right) { //在比较 Integer 类型的值时，使用 equals() 比较更合适 if (!values.get(left).equals(values.get(right))) { return false; } else { //移动指针 left++; right--; } } return true; } } 

//思路2————双指针 /**
 * Definition for singly-linked list.
 * 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; }
 * }
 */ class Solution { public boolean isPalindrome(ListNode head) { ListNode left = head; ListNode right = reverse(middleNode(head)); while (right != null) { if (left.val != right.val) { return false; } else { left = left.next; right = right.next; } } return true; } //查找链表的中间节点 public ListNode middleNode(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } //反转链表 public ListNode reverse(ListNode head) { ListNode prev = null; ListNode curr = head; ListNode next; while (curr != null) { next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } }