234. Palindrome Linked List #

题目 #

给定单链表的头节点head，判断该链表是否为回文链表。

考虑使用O(n)时间复杂度和O(1)空间复杂度解决此题。

思路 #

分割、翻转 #

使用快慢指针找到链表中心节点。
- 如果链表长度为偶，则fast.next == null时，slow指向链表前半部分的最后一个节点。
- 如果链表长度为奇，则fast == null时，slow指向链表的轴节点。
使用迭代的方式以O(1)空间复杂度翻转链表的后半部分。
判断链表是否为回文链表。
将后半部分链表恢复原状，避免对链表的破坏。
返回结果。

代码 #

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 ListNode locateMiddle(ListNode head) {
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public ListNode reverseList(ListNode head) {
        ListNode prev = null, cur = head, next = head.next;
        while (cur != null) {
            cur.next = prev;
            prev = cur;
            cur = next;
            if (next != null) next = next.next;
        }
        return prev;
    }
    public boolean compareList(ListNode ptrA, ListNode ptrB) {
        while (ptrA != null && ptrB != null) {
            if (ptrA.val != ptrB.val) return false;
            ptrA = ptrA.next;
            ptrB = ptrB.next;
        }
        return true;
    }
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;
        ListNode middle = locateMiddle(head);
        ListNode tail = reverseList(middle.next);
        boolean isConsistent = compareList(head, tail);
        reverseList(middle.next);
        return isConsistent;
    }
}