Katkat
Back

Check Whether a Singly Linked List Is a Palindrome

OmnissaSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

Tests the ability to determine if a singly linked list is a palindrome in O(n) time and O(1) auxiliary space using two pointers and in-place list reversal.

Problem Statement

Given the head of a singly linked list, determine whether the sequence of values in the list forms a palindrome (i.e., reads the same forwards and backwards).

To meet the performance requirements, your solution must achieve O(n) time complexity and O(1) auxiliary space complexity. Modifying the list in place (such as reversing a portion of it) is permitted, but the structure should ideally be restored to its original state before returning.

Class Definition

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

Function Signature

def is_palindrome(head: Optional[ListNode]) -> bool:
    pass

Examples

Example 1:

Input: head = [1, 2, 2, 1]
Output: True
Explanation: The sequence of values [1, 2, 2, 1] reads the same forwards and backwards.

Example 2:

Input: head = [1, 2, 3, 2, 1]
Output: True
Explanation: The sequence of values [1, 2, 3, 2, 1] is symmetric around the center node (3).

Example 3:

Input: head = [1, 2]
Output: False
Explanation: 1 != 2, so it is not a palindrome.

Constraints

  • The number of nodes in the list is in the range [0, 10^5].
  • 0 <= Node.val <= 9
  • Time Complexity: O(n)
  • Auxiliary Space Complexity: O(1)

Edge Cases

  • An empty list (head is None) or a single node list should be considered a valid palindrome (True).
  • Lists with an odd number of elements where the middle node does not need a pairing.
  • Lists with two nodes (e.g., [1, 1] vs [1, 2]).

Hints

Hint 1

Use a fast and slow pointer technique to locate the midpoint (or the start of the second half) of the list in a single pass.

Hint 2

Reverse the second half of the linked list in place using three pointers (prev, curr, next) to avoid extra space.

Hint 3

Compare nodes sequentially from the start of the list and the start of the reversed second half, and consider reversing the second half back before returning.

Follow-up questions

  • How would you ensure thread safety if multiple threads need to read this list concurrently while you are modifying pointers?
  • Could this be solved recursively without modifying the list, and what would the resulting space complexity be?
  • How does the implementation change if the input is a doubly linked list instead of a singly linked list?