Check Linked List Palindrome

EasyPython

Problem

Applied Network Solutions uses singly linked lists to represent ordered packet-processing stages. Write a function that determines whether the sequence of stage values reads identically from left to right and right to left.

Return True when the linked list is a palindrome and False otherwise. Your preferred solution must run in O(n) time and use O(1) auxiliary space. The list should be restored to its original order before the function returns.

Formal Specification

The input is head, either None or a reference to the first node of a singly linked list. Each node has an integer val field and a next field containing another node or None. Return a Boolean.

For the JSON test cases below, each input array represents the linked list from head to tail. The test harness converts the array into linked nodes before calling the function.

Constraints

0 <= n <= 10^5
-10^9 <= node.val <= 10^9
The input is a singly linked list
The list must be restored before the function returns

Function Signature

def is_palindrome(head):

Formal Specification

For the JSON test cases below, each input array represents the linked list from head to tail. The test harness converts the array into linked nodes before calling the function.