Palindrome Linked List easy

Problem Statement

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

Example 1

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

Example 2

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

Steps

1. Find the middle of the linked list: We'll use the slow and fast pointer technique. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. When the fast pointer reaches the end, the slow pointer will be at the middle.

2. Reverse the second half of the linked list: We'll reverse the linked list starting from the middle node.

3. Compare the first half and the reversed second half: We'll iterate through the first half and the reversed second half, comparing nodes one by one. If all nodes match, it's a palindrome; otherwise, it's not.

Explanation

The algorithm efficiently determines if a linked list is a palindrome without requiring extra space proportional to the list's length (apart from a few pointers). The slow/fast pointer method elegantly finds the middle in O(N) time. Reversing the second half also takes O(N) time. The final comparison is O(N/2), which simplifies to O(N). Therefore, the overall time complexity is O(N). Space complexity is O(1) because we're using only a constant number of extra variables.

Code

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def isPalindrome(head):
    # Find the middle of the linked list
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Reverse the second half of the linked list
    prev = None
    curr = slow
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    # Compare the first half and the reversed second half
    first_half = head
    second_half = prev
    while second_half:
        if first_half.val != second_half.val:
            return False
        first_half = first_half.next
        second_half = second_half.next
    return True

#Example Usage
head = ListNode(1, ListNode(2, ListNode(2, ListNode(1))))
print(isPalindrome(head)) # Output: True

head = ListNode(1, ListNode(2))
print(isPalindrome(head)) # Output: False

Complexity

• Time complexity: O(N), where N is the number of nodes in the linked list.
• Space complexity: O(1) – constant extra space is used.