234. 回文链表

本题来自 LeetCode：234. 回文链表^[1]

题目描述

请判断一个链表是否为回文链表。
示例 1:

输入: 1-2
输出: false

示例 2:

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

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

题目分析

先采用快慢指针，将链表分成相等的两段（长度为奇数时，第一段链表长度比第二段长度大 1）；

将第二段链表反转；

比较两段链表，比较两段链表相同长度的部分是否相等；

题目解答

/**
 * 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 dummy = new ListNode(-1);
        dummy.next = head;
        ListNode fast = dummy;
        ListNode slow = dummy;
        // 链表长度为偶数
        while(fast != null) {
            fast = fast.next;
            if(fast == null) {
                // 链表长度为奇数
                break;
            }
            fast = fast.next;
            slow = slow.next;
        }

        // 将链表截成两段
        ListNode second = slow.next;
        slow.next = null;
        // 将第二段链表反转
        second = reverse(second);
        // 链表长度为奇数时，第一段链表长度比第二段长度大1
        // 链表长度为偶数时，两段链表长度相等
        return comparePrefix(dummy.next, second);
    }

    // 比较两段链表相同长度的部分是否相等
    public boolean comparePrefix(ListNode node1, ListNode node2) {
        while(node2 != null) {
            if(node1.val != node2.val) {
                return false;
            }
            node1 = node1.next;
            node2 = node2.next;
        }
        return true;
    }

    // 反转链表
    public ListNode reverse(ListNode head) {
        ListNode dummy = new ListNode(-1);
        dummy.next = null;

        while(head != null) {
            ListNode temp = head;
            head = head.next;

            temp.next = dummy.next;
            dummy.next = temp;
        }

        return dummy.next;
    }
}

复杂度分析：
时间复杂度： O(n)；
空间复杂度： O(1)；

参考资料

234. 回文链表: https://leetcode-cn.com/problems/palindrome-linked-list/

原文始发于微信公众号（xiaogan的技术博客）：