234. Palindrome Linked List

Easy

Problem:

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

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

https://leetcode.com/problems/palindrome-linked-list/

What to learn:

List pop(index)

• The pop() method takes a single argument (index) and returns the item present at the given index. This item is also removed from the list.

• The argument passed to the method is optional. If not passed, the default index -1 is passed as an argument (index of the last item).

• If the index passed to the method is not in range, it throws IndexError: pop index out of range exception.

Runner

The Runner technique is a method used when traversing a linked list, where two pointers are used simultaneously.

• Generally, the fast runner (pointer) skips two steps while the slow runner (pointer) moves one step at a time.

• When the fast runner reaches the end of the linked list, the slow runner will be pointing exactly to the midpoint of the linked list.

• This method of finding the midpoint allows us to compare values, attempt reversals, and do much more from that point onwards.

Therefore, this technique is essential and widely used in problems related to linked lists.

Solution:

To determine whether it is a palindrome, a data structure that can extract from both the front and the back is needed.

List

The linked list input is converted into a Python list for the solution.

# 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:
        q: List = []

        if not head:
            return True

        node = head
        while node is not None:
            q.append(node.val)
            node = node.next

        while len(q) > 1:
            if q.pop(0) != q.pop():
                return False

        return True

Deque

The list constructed as a dynamic array is not a suitable data type for fetching the first item. This is because if you take out the first value, all the values shift by one place, resulting in a time complexity of $O(n)$.

Python's Deque is a doubly linked list structure that can extract from both directions with a time complexity of $O(1)$.

# 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:
        q: Deque = collections.deque()

        if not head:
            return True

        node = head
        while node is not None:
            q.append(node.val)
            node = node.next

        while len(q) > 1:
            if q.popleft() != q.pop():
                return False

        return True

Runner

# 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:
        rev = None
        slow = fast = head
        
        while fast and fast.next:
            fast = fast.next.next
            rev, rev.next, slow = slow, rev, slow.next
            
        # Odd length = the fast runner is not yet None
        if fast:
            slow = slow.next
        
        # Check Palindrome
        while rev and rev.val == slow.val:
            slow, rev = slow.next, rev.next
        return not rev