:orphan:

Palindrome Linked List
======================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/palindrome-linked-list/

Given the ``head`` of a singly linked list, return ``true`` *if it is a*
palindrome *or* ``false`` *otherwise*.

 

**Example 1:**

|image1|

::


   Input: head = [1,2,2,1]
   Output: true

**Example 2:**

|image2|

::


   Input: head = [1,2]
   Output: false

 

**Constraints:**

- The number of nodes in the list is in the range
  ``[1, 10``\ :sup:```5```\ ``]``.
- ``0 <= Node.val <= 9``

 

**Follow up:** Could you do it in ``O(n)`` time and ``O(1)`` space?

.. |image1| image:: https://assets.leetcode.com/uploads/2021/03/03/pal1linked-list.jpg
.. |image2| image:: https://assets.leetcode.com/uploads/2021/03/03/pal2linked-list.jpg

.. highlight:: python

Pattern
-------
Linked List, Two Pointers, Stack, Recursion

Solution
--------
Save the contents of the linked list in a regular list ``list``. Then, use two
pointers``i`` and ``j`` to check if ``list`` is a palindrome, moving them
inwards if ``list[i] == list[j]``.

Code
----

.. literalinclude:: ../problems/easy/palindrome-linked-list/palindrome_linked_list__approach_1.py
    :language: python
    :lines: 11-

Test
----
>>> from palindrome_linked_list__approach_1 import ListNode, isPalindrome
>>> head = ListNode.from_list([1, 2, 2, 1])
>>> isPalindrome(head)
True
>>> head = ListNode.from_list([1, 2])
>>> isPalindrome(head)
False

Complexity
----------
| :math:`n` is the number of nodes in the linked list
| Time: :math:`O(n)` — traverse list twice
| Auxiliary Space: :math:`O(n)` — store linked list values in list

.. autoclass:: palindrome_linked_list__approach_1.ListNode
   :members:
   :show-inheritance:
   :undoc-members:

.. autofunction:: palindrome_linked_list__approach_1.isPalindrome