回文链表 | 徐年の博客

力扣 234. 回文链表

题目说明

请判断一个链表是否为回文链表。
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

示例

示例 1:

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

示例 2:

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

笔者理解

此题是一道二维数组算法问题，在力扣题库中被定义为简单题。

解法

当笔者阅读完此题后，发现此题的原地算法需要使用到快慢指针加反转链表，通过先找到中间节点，再对之后的链表进行反转，最后将反转后的链表和前面的进行比较，都相同的就是回文链表，让我们来看看具体如何实现的吧。

实现

/**
 * 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 fast = head;
        ListNode slow = head;

        // 通过快指针一次走两步，而慢指针一次走一步的操作来寻找中间节点
        while (fast != null) {
            slow = slow.next;

            // 注意判空，如果快指针只能走一步了，那就走一步
            fast = fast.next == null? fast.next: fast.next.next;
        }

        // 反转链表
        ListNode pre = null;
        while (slow != null) {
            ListNode temp = slow.next;
            slow.next = pre;
            pre = slow;
            slow = temp;
        }

        // 比较后半截反转后的链表是否和前半截相同
        // 只比较相同长度
        while (head != null && pre != null) {
            if (head.val != pre.val) {
                return false;
            }
            head = head.next;
            pre = pre.next;
        }

        return true;
    }
}