Slow and Fast Pointers: 234. Palindrome Linked List

Question:

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?

Solution:

• Break the original linkedlist at the middle. (Make sure the node that becomes the head of the later half is correctly identified).
• Reverse the later half of the original LinkedList.
• Iterate through both the halves of the linkedlist;
  • If any element is unequal whilst being at the same position (read index) of both LinkedLists, then return false. Original List is not palindrome in this case.
• If we don't find any such element, then return true. List is indeed Palindromic.

Code:

class Solution {
    public boolean isPalindrome(ListNode head) {

        if(head.next == null) return true;

        ListNode mid = findMiddle(head), secondHead = mid.next;

        ListNode newHead = reverse(secondHead);

        while(newHead != null){
            if(head.val == newHead.val) {
                head = head.next;
                newHead = newHead.next;
            }
            else return false;
        }

        return true;

    }


    static ListNode reverse(ListNode head){

        ListNode prev = null, curr = head, next = curr.next;

        while(curr != null){

            curr.next = prev;
            prev = curr;
            curr = next;

            if(curr == null) break;
            else next = curr.next;

        }

        return prev;

    }

    static ListNode findMiddle(ListNode head){

        ListNode slow = head, fast = head.next;

        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;

        }

        return slow;


    }
}

Complexity:

• Time: O(N)
• Space: O(1)