234. Palindrome Linked List (Easy)

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

Given a singly linked list, determine if it is a palindrome.

Example 1:

Input: 1->2
Output: false

Example 2:

Input: 1->2->2->1
Output: true

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

Solutions

1.

class Solution {

    // Recursive method.

    ListNode headx = null;
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        headx = head;

        return recurse(head);
    }

    private boolean recurse(ListNode ptr) {
        if (ptr == null) {
            return true;
        }

        boolean rst = recurse(ptr.next);
        if (!rst) {
            return false;
        }

        if (headx.val != ptr.val) {
            return false;
        }

        headx = headx.next;

        return true;
    }
}

2.

class Solution {

    // Non-recursive method. Modify the list that move nodes on the right to head. Such that
    // the elements of right part are in reverse order.

    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) {
            return true;
        }

        ListNode tmp = head;
        // find out the length of the list
        int len = 0;
        while (tmp != null) {
            tmp = tmp.next;
            len++;
        }

        // reverse the front half of the list

        int mid = len / 2;

        // head->pointer->px

        // right points to the swapped node
        // left is one step prior to right pointer
        ListNode left = head;
        ListNode right = left.next;
        for (int i = 1; i < mid; i++) {
            // move away the node pointed by right pointer
            left.next = right.next;

            // make the right node pointing to the head
            right.next = head;

            // then make right pointer one step after left pointer
            head = right;
            right = left.next;
        }

        // prepare 2 pointers of which one points the head and another points the middle
        ListNode p1 = head;
        ListNode p2 = head;

        // p2Idx starts from 1
        int p2Idx = mid + 1;
        if (len % 2 == 1) {
            p2Idx += 1;
        }

        // Move p2Idx-2 steps to reach desired position
        for (int i = 0; i < p2Idx - 1; i++) {
            p2 = p2.next;
        }

        // Move on the 2 pointers simultaneously and meanwhile compare the values. Once come
        // across different values, representing the list is not palindrome.

        while (p1 != null && p2 != null) {
            if (p1.val != p2.val) {
                return false;
            }

            p1 = p1.next;
            p2 = p2.next;
        }

        return true;
    }
}

Incorrect Solutions

References