Quick Overview

Construct a singly linked list and test whether its values form a palindrome. The exercise requires linear time and constant auxiliary space for the check, encouraging midpoint discovery, partial reversal, careful odd-length handling, and value comparison.

Check Whether a Singly Linked List Is a Palindrome

Company: Omnissa

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

# Check Whether a Singly Linked List Is a Palindrome Given the values of a singly linked list in head-to-tail order, construct the linked list and determine whether its values form a palindrome. Implement: ```text isLinkedListPalindrome(values) -> boolean ``` Use a singly linked `Node` structure with `value` and `next` fields. The palindrome check must run in `O(n)` time and use `O(1)` auxiliary space after the list has been constructed. You may reverse part of the list in place. The empty list is considered a palindrome. ## Constraints - `0 <= values.length <= 1,000,000` - `-10^9 <= values[i] <= 10^9` ## Examples ### Example 1 ```text values = [1, 2, 3, 2, 1] output = true ``` ### Example 2 ```text values = [1, 2, 2, 3] output = false ```

Overview: Construct a singly linked list and test whether its values form a palindrome. The exercise requires linear time and constant auxiliary space for the check, encouraging midpoint discovery, partial reversal, careful odd-length handling, and value comparison.

Read the full Omnissa Software Engineer interview experience this question came from

Given values in head-to-tail order, construct a singly linked list whose Node objects have value and next fields, then return whether its values form a palindrome. The palindrome check must run in O(n) time with O(1) auxiliary space after construction; reversing part of the list in place is allowed. The empty list is a palindrome.

Constraints

  • 0 <= values.length <= 1,000,000
  • -10^9 <= values[i] <= 10^9
  • The empty list is a palindrome.
  • After list construction, the check must use O(1) auxiliary space.

Examples

Input: ([1, 2, 3, 2, 1],)

Expected Output: True

Explanation: The values read the same from head to tail and tail to head.

Input: ([1, 2, 2, 3],)

Expected Output: False

Explanation: The first and last values already differ.

Hints

  1. Use fast and slow pointers to find the midpoint without storing node values separately.
  2. Reverse the first half while advancing the midpoint pointers, then compare the two halves.

Loading coding console...

Show the approach

Approach

Construct the linked list in the supplied order. During a fast/slow-pointer scan, reverse the first half one link at a time. When the fast pointer reaches the end, slow starts the second half for even length; for odd length, skip its middle node. Compare the reversed first half with the second half. The check keeps only a fixed number of pointers after the list exists.

Time complexity:
O(n) time for construction and the palindrome check.
Space complexity:
O(n) space for the constructed list and O(1) auxiliary space during the palindrome check.