Palindrome Linked List

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Given a linked list, check whether it is a palindrome

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Need to solve this in $O(1)$ space complexity

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Linked List

Time & Space Complexity

• Time: $O(n)$ → Reason: Iterating through each item in the list
• Space: $O(n)$ → Reason: Storing a copy of the list

Code

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

        l, r = 0, len(list) - 1

        while l < r:
            if list[l] != list[r]:
                return False
            l += 1
            r -= 1

        return True
        # Time: O(n)
        # Space: O(n)

Time & Space Complexity of the Optimized COde

• Time: $O(n)$ → Reason: Iterating through each item in the list
• Space: $O(1)$ → Reason: Not storing another copy

Optimized Code

# 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:
        # get to the middle
        # reverse second half
        # check each pointer
        # if we reach middle then return True
        if not head:
            return True
        slow, fast = head, head.next
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
        
        # 1,2,1,2
        #   s,  f
        #     m
        #       p c
        # reverse from slow.next

        middle = slow.next
        prev, cur = None, middle

        while cur:
            next = cur.next
            cur.next = prev
            prev, cur = cur, next
        # start of reversed list is prev
        # 1,2,1,2
        # l   r
        leftStart = head
        rightStart = prev
        while leftStart and rightStart:
            if leftStart.val != rightStart.val:
                return False
            leftStart, rightStart = leftStart.next, rightStart.next
        return True