0234. Palindrome Linked List

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

Description

Given the head of a singly linked list, return true if it is a palindrome.

Example 1:

**Input:** head = [1,2,2,1]
**Output:** true

Example 2:

**Input:** head = [1,2]
**Output:** false

Constraints:

• The number of nodes in the list is in the range [1, 105].

• 0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space?

ac

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        // edge cases
        if (head == null || head.next == null) return true;

        // 2 pointers
        ListNode slow = head.next, fast = head.next.next, r = head, prev = null;
        int cnt = 2;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            cnt += 2;
            // reverse 
            r.next = prev;
            prev = r;
            r = slow;
            slow = slow.next;
        }
        r.next = prev;
        if (fast != null) cnt++;

        // check
        ListNode left = r, right = cnt % 2 == 0 ? slow : slow.next;
        while (left != null && right != null) {
            if (left.val != right.val) return false;
            left = left.next;
            right = right.next;
        }

        return true;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        // edge cases
        if (head == null || head.next == null) return true;

        // 2 pointers, fast/slow, reverse first half
        ListNode fast = head, slow = head, prev = null;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;

            ListNode tmp = slow.next;
            slow.next = prev;
            prev = slow;
            slow = tmp;
        }

        // left and right side
        ListNode left = prev;
        ListNode right = fast == null ? slow : slow.next;

        // validate
        while (left != null && right != null) {
            if (left.val != right.val) return false;
            left = left.next;
            right = right.next;
        }

        return true;
    }
}