234. Palindrome Linked List (Python)

Related Topic

Linked-List.

Description

Given a singly linked list, determine if it is a palindrome.

Follow Up:

What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Sample I/O

Example 1

Input: 1->2
Output: false

Example 2

Input: 1->2->2->1
Output: true

Follow Up

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

Methodology

There are many ways to solve the problem.

1. We can iterate the whole linked list and store each value into list, then we compare the list and reversed list if they are same then the linked list is palindrome.
2. We can use fast slow pointer to find the middle point and reverse the first half or second half to compare with the other half.

Code

solution 1

def isPalindrome(self, head: ListNode) -> bool:
        vals = []
        current_node = head
        while current_node is not None:
            vals.append(current_node.val)
            current_node = current_node.next
        return vals == vals[::-1]

BigO

Iterate the linked list once, so total time complexity is O(n)

solution 2

def isPalindrome(self, head: ListNode) -> bool:
        fast = slow = head
        stak = []
        while fast and fast.next:
            stak.append(slow.val)
            slow = slow.next
            fast = fast.next.next
        if fast:
            slow = slow.next
        while slow:
            top = stak.pop()
            if top != slow.val:
                return False
            slow = slow.next
        return True

BigO

Iterate the linked list once, so total time complexity is O(n)