EasyNo. 0234

Palindrome Linked List — LeetCode 234 Python Solution

Topics
Stack, Recursion, Linked List, Two Pointers
Reading time
3 min

The problem

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

Example

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

Python solution

PythonSolution
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head.next
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        pre, cur = None, slow.next
        while cur:
            t = cur.next
            cur.next = pre
            pre, cur = cur, t
        while pre:
            if pre.val != head.val:
                return False
            pre, head = pre.next, head.next
        return True

Complexity

Time
O(n)where n is the length of the linked list
Space · auxiliary
O(1)

Pattern: Linked List

Rewire pointers in place, with a dummy head and a saved next to keep it safe. LeetCode 234. Palindrome Linked List is filed here because LeetCode tags it Linked List, which is the vocabulary this hub collects.

The linked list guide has the Python template for the pattern and the 75 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0143Reorder ListMedium
2130Maximum Twin Sum of a Linked ListMedium
0224Basic CalculatorHard
0042Trapping Rain WaterHard
0114Flatten Binary Tree to Linked ListMedium
0321Create Maximum NumberHard

Frequently asked questions

How hard is LeetCode 234. Palindrome Linked List?

LeetCode 234. Palindrome Linked List is rated Easy on LeetCode.

What is the time complexity of LeetCode 234. Palindrome Linked List?

The Python solution on this page runs in O(n), where n is the length of the linked list.

What is the space complexity of LeetCode 234. Palindrome Linked List?

The Python solution on this page uses O(1) auxiliary space.

What topics does LeetCode 234. Palindrome Linked List cover?

LeetCode 234. Palindrome Linked List is tagged Stack, Recursion, Linked List and Two Pointers on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.