We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Palindrome Linked List

Difficulty: Easy

Problem Description

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

Key Insights

  • A palindrome reads the same forwards and backwards.
  • We need to compare the first half of the linked list with the reversed second half.
  • Efficiently solve the problem in O(n) time and O(1) space using the fast and slow pointer technique.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

To determine if a linked list is a palindrome, we can use a two-pointer technique to find the middle of the list. The slow pointer moves one step at a time, while the fast pointer moves two steps. When the fast pointer reaches the end, the slow pointer will be at the middle. We then reverse the second half of the list and compare it with the first half.

  1. Use two pointers to find the middle of the list.
  2. Reverse the second half of the list.
  3. Compare the first half and the reversed second half.
  4. Restore the original list (if needed).
  5. Return true if they are equal, otherwise false.

Code Solutions

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

def isPalindrome(head: ListNode) -> bool:
    if not head or not head.next:
        return True

    # Step 1: Find the middle of the linked list
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # Step 2: Reverse the second half of the list
    prev = None
    while slow:
        next_temp = slow.next
        slow.next = prev
        prev = slow
        slow = next_temp

    # Step 3: Compare the first and second halves
    left, right = head, prev
    while right:  # Only need to check the right half
        if left.val != right.val:
            return False
        left = left.next
        right = right.next

    return True
← Back to All Questions