234-palindrome-linked-list

Date created: 2025-05-03-Sat 18:39

Question Description

Given the head of a singly linked list, return true if it is a

or false otherwise.

Example 1:

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

Example 2:

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

Constraints:

The number of nodes in the list is in the range [1, 105].
0 <= Node.val <= 9

Follow up: Could you do it in O(n) time and O(1) space? Seen this question in a real interview before?

problem link

solution video link

Thought Process

  • Don’t be fooled by the easy tag, this is at least medium considering the amount of code and thought process!

  1. everytime when I see a reverse problem, and it’s involing linked-list, I’ll imediately thinking about fast slow potiner

  2. we use the fast slow potiner to find the mid

  3. then we reverse the second half of the linked list

#          1 -> 2 -> 3
# prev    cur
#------------------------
#       <- 1     2 -> 3
# prev    cur  next
#------------------------
#      <- 1 <-  2 -> 3
#        prev  cur  next

key code snippet:


# change direction of the pointer
next_node = cur.next
cur.next = prev

# go to next node, do the same thing
prev = cur
cur = next_node

Code

class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        """Fast slow ptr.

        slow will eventually goes to mid fast will point to end and we
        have start ptr so we then can compare start and fast ptr just
        like what we did for regular list mid will be at slow ptr
        """
        fast, slow = head, head
        while fast and fast.next:
            fast = fast.next
            fast = fast.next
            slow = slow.next

        # we can reverse the 2nd half of the list , if it's palindrome, 2nd half will be like 1st half if reversed
        cur, prev = slow, None

        # reverse
        while cur:

            # fmt: off
            #          1 -> 2 -> 3
            # prev    cur
            #------------------------
            #       <- 1     2 -> 3
            # prev    cur  next
            #------------------------
            #      <- 1 <-  2 -> 3
            #        prev  cur  next
            # fmt: on

            next_node = cur.next
            cur.next = prev
            prev = cur
            cur = next_node
            
        # print("===second half list after reversing the 2nd half===")
        # print_list(prev)  # prev is now the head of the reversed second half
        # print("===second half list after reversing the 2nd half===")
        #
        # now the second half is exactly same as first half(if it's palindrome)
        ptr = head
        while prev:
            if ptr.val != prev.val:
                return False
            ptr = ptr.next
            prev = prev.next
                    
        # the reversed second half has same values as the first half
        return True

Time/Space Complexity

  • Time: \( O(n) \) since \( O(n) \) to find the mid + \( O(n) \) to use two-pointer technique to reverse the second-half of the linked list

  • Space: \( O(1) \) since we are not using any extra space, just pointers