noodleProblems/
Palindrome Linked List
#110

Palindrome Linked List

AlgorithmeasyLinked ListTwo PointersStackRecursion

Given the head of a singly linked list, return true if the list reads the same forwards and backwards, and false otherwise.

Your function receives a ListNode chain; the examples show each list in array notation for readability — [1, 2, 2, 1] is the chain 1 -> 2 -> 2 -> 1, which is a palindrome.

Aim for O(n) time and O(1) extra space.

Example cases

  • even palindrome
    in head = [1,2,2,1]1221null
    out true
    Reads the same both ways.
  • not a palindrome
    in head = [1,2]12null
    out false
    1->2 reversed is 2->1, which differs.
  • odd palindrome
    in head = [1,2,3,2,1]12321null
    out true

Constraints

  • The number of nodes in the list is in the range [1, 100000].
  • 0 <= Node.val <= 9
Saved
head =
[1,2,2,1]