Palindrome linked list
You get head, the first node of a linked list of integers, or None if the list is empty. Each node is a ListNode with a value (node.val) and a link (node.next) to the node after it.
Return True if the values read the same from front to back as from back to front, and False otherwise. A list like that is a palindrome. An empty list and a one-node list count as palindromes.
You may relink nodes while you check: the tests look only at the True or False you return. Examples write a linked list as the list of its values: [4, 7, 7, 4] means 4 → 7 → 7 → 4.
head = [4, 7, 7, 4]OutputTrueBoth directions read 4, 7, 7, 4.
head = [2, 5, 9, 5, 2]OutputTrueThe middle 9 has no partner, so it cannot break the match.
head = [1, 2, 3, 1]OutputFalseThe ends match, but the second value 2 differs from the second-to-last value 3.
0 ≤ number of nodes ≤ 105
Node values are integers.
Plan it first
Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.