Palindrome Linked List Coding

EasyPython

Problem

NASA Jet Propulsion Laboratory telemetry pipelines may represent an ordered sequence of readings as a singly linked list. Given the head of such a list, determine whether the sequence reads identically from left to right and right to left.

Return True if the list is a palindrome and False otherwise. Your solution should run in linear time and use constant auxiliary space. You may temporarily modify the list, but restore its original structure before returning.

Formal Specification

Implement is_palindrome(head), where head is either None or a ListNode. Each node has an integer val field and a next field containing the next node or None. The function returns a Boolean.

For the test cases below, the input array lists node values from head to tail. The test harness constructs the corresponding linked list before calling the function.

Constraints

0 <= n <= 10^5
-10^9 <= node.val <= 10^9
The list contains no cycles
The function should use O(1) auxiliary space

Function Signature

def is_palindrome(head):

Formal Specification

For the test cases below, the input array lists node values from head to tail. The test harness constructs the corresponding linked list before calling the function.