回文链表

1、参考资料

https://leetcode-cn.com/problems/palindrome-linked-list/

2、题目

题目要求

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

示例 1：

输入：1->2

输出：false

示例 2:

输入: 1->2->2->1

输出: true

进阶：

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

3、代码思路

方法一：

遍历链表，将其中的数据存入 ArrayList 中，然后对 ArrayList 进行回文判断即可(双指针法)遍历整个链表，将其添加至 ArrayList 中的时间复杂度为 O(n)，因为 ArrayList 底层使用数组存储，访问任一元素的时间复杂度为 O(1)，使用双指针法判回文的时间复杂度为 O(n/2)，所以整个算法复杂度为 O(n)因为额外开辟了 ArrayList 的空间，所以需要额外 O(n) 的空间

---

方法二：

想要将空间复杂度降为 O(1)，意思就是要在原链表上进行回文判断，我们可以将链表的后半部分反转(修改链表结构)，然后将前半部分和后半部分进行比较。首先，我们需要找到中间的链表节点，对此我们可以使用两种方法：第一，先求得链表长度，除以 2 便得到中间节点的索引；第二，使用快慢指针，慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针到链表的中间然后翻转后半部分的链表，同时从链表首部和中间遍历，挨个比较各个节点的值，判断链表是否回文链表恢复链表，虽然不需要恢复也能通过测试用例，因为使用该函数的人不希望链表结构被更改。

---

方法三：

4、代码实现

方法一：

/** * @ClassName IsPalindromeDemo * @Description TODO * @Author Heygo * @Date 2020/9/2 20:41 * @Version 1.0 */ public class IsPalindromeDemo { public static void main(String[] args) { ListNode head = new ListNode(129); head.next = new ListNode(129); boolean isPalindrome = isPalindrome(head); System.out.println(isPalindrome); } /** * 判断链表是否为回文链表 * @param head 链表首节点 * @return true：回文链表；false：不是回文链表 */ public static boolean isPalindrome(ListNode head) { // 将链表中的值加入到 ArrayList 中 List<Integer> vals = new ArrayList<>(); ListNode curNode = head; while (curNode != null) { vals.add(curNode.val); curNode = curNode.next; } // 双指针判断回文数组 int left = 0; int right = vals.size() - 1; while (left < right) { if (vals.get(left).equals(vals.get(right))) { left++; right--; } else { return false; } } return true; } public static class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } }

---

方法二：

/** * @ClassName IsPalindromeDemo * @Description TODO * @Author Heygo * @Date 2020/9/2 20:41 * @Version 1.0 */ public class IsPalindromeDemo { public static void main(String[] args) { ListNode head = new ListNode(1); head.next = new ListNode(2); head.next.next = new ListNode(2); head.next.next.next = new ListNode(1); boolean isPalindrome = isPalindrome(head); System.out.println(isPalindrome); } /** * 判断链表是否为回文链表 * @param head 链表首节点 * @return true：回文链表；false：不是回文链表 */ public static boolean isPalindrome(ListNode head) { // 获取中间节点 ListNode middleNode = findMiddleNode(head); // 翻转后半部分链表 ListNode secondHead = reverse(middleNode); // 前半部分与后半部分相比较 ListNode frontPointer = head; ListNode backPointer = secondHead; while (backPointer != null) { if (frontPointer.val == backPointer.val) { frontPointer = frontPointer.next; backPointer = backPointer.next; } else { return false; } } return true; } /** * 找出链表中间的节点， * 如果链表长度为 n，则返回第 n/2 个节点，索引从 0 开始 * * @param head 链表首节点 * @return 中间节点 */ public static ListNode findMiddleNode(ListNode head) { ListNode slow = head; ListNode fast = head; // fast 每走两步，slow 走一步 while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } /** * 翻转链表 * @param head 链表首节点 * @return 翻转后的链表首节点 */ public static ListNode reverse(ListNode head) { ListNode pre = null; ListNode cur = head; while (cur != null) { // 保存 cur.next ListNode tempNode = cur.next; // 让 cur 指向 pre cur.next = pre; // pre 指针后移 pre = cur; // cur 指针后移 cur = tempNode; } // 遍历完后，cur == null，pre 恰好指向新的链表头 return pre; } public static class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } }

``