234.md

234. Palindrome Linked List

Description

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

Thinking Process

1. The trick to achive O(1) space complexity is to only reverse half of the list and compare it against the other half
2. Use two pointers to find the middle point of the list, then reverse the second half
3. Compare the first half and the second half. (difference between lengths of the two halves must be less than 2)

Code

public class Solution {
    public boolean isPalindrome(ListNode head) {
        if(head == null)
            return true;
        ListNode slow = head;
        ListNode fast = head;
       	//find the middle point of the list
        while(fast != null){
            slow = slow.next;
            fast = fast.next != null ? fast.next.next : null;
        }
     	//reverse the second half of the list
        ListNode secondHalf = reverse(slow);
        while(secondHalf != null){
            if(secondHalf.val != head.val){
                return false;
            }
            secondHalf = secondHalf.next;
            head = head.next;
        }
        return (head == slow || head.next == slow);
    }
    
    ListNode reverse(ListNode head){
        ListNode prev = null;
        while(head != null){
            ListNode nextNode = head.next;
            head.next = prev;
            prev = head;
            head = nextNode;
        }
        return prev;
    }
}

Complexity

1. Space complexity is O(1), since no additional data structures are required
2. Time complexity is O(n) since the list is scanned three times (find the middle point, reverse second half, compare two halves)