234. Palindrome Linked List - Explanation

Description

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

A palindrome is a sequence that reads the same forward and backward.

Example 1:

Input: head = [1,2,3,2,1]

Output: true

Example 2:

Input: head = [2,2]

Output: true

Example 3:

Input: head = [2,1]

Output: false

Constraints:

1 <= Length of the list <= 100,000.
0 <= Node.val <= 9

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

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Convert To Array

# 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:
        arr = []
        cur = head
        while cur:
            arr.append(cur.val)
            cur = cur.next

        l, r = 0, len(arr) - 1
        while l < r:
            if arr[l] != arr[r]:
                return False
            l, r = l + 1, r - 1

        return True

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Recursion

# 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:
        self.cur = head

        def rec(node):
            if node is not None:
                if not rec(node.next):
                    return False
                if self.cur.val != node.val:
                    return False
                self.cur = self.cur.next
            return True

        return rec(head)

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for recursion stack.

3. Stack

# 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:
        stack = []
        cur = head

        while cur:
            stack.append(cur.val)
            cur = cur.next

        cur = head
        while cur and cur.val == stack.pop():
            cur = cur.next

        return not cur

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Fast & Slow Pointers

# 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: ListNode) -> bool:
        fast = head
        slow = head

        # find middle (slow)
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        # reverse second half
        prev = None
        while slow:
            tmp = slow.next
            slow.next = prev
            prev = slow
            slow = tmp

        # check palindrome
        left, right = head, prev
        while right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next

        return True

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$ extra space.