EasyLinked Lists

Palindrome Linked List

Check if linked list is palindrome

Solution Approach

Find middle with slow/fast pointers, reverse second half, then compare both halves.

Implementation

def isPalindromeList(head):
    if not head or not head.next:
        return True
    
    # Find middle
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # Reverse second half
    prev = None
    while slow:
        next_node = slow.next
        slow.next = prev
        prev = slow
        slow = next_node
    
    # Compare
    left, right = head, prev
    while right:  # right will be shorter
        if left.val != right.val:
            return False
        left = left.next
        right = right.next
    return True

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)

Complexity

Time:O(n)

Space:O(1)

Asked at

GoogleFacebook