Teaching Kids Programming – Algorithms to Check if a Linked List is Palindrome

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a singly linked list node whose values are integers, determine whether the linked list forms a palindrome.

Constraints
n ≤ 100,000 where n is the length of node

For example, 1 – 2 – 3 is not a palindrome linked list but 1 – 2 – 1 is

Linked List Palindrome via Conversion to List

Most Linked List problems can be solved by converting the linked list to a normal list (using O(N) space) so that we can random access the element in the list using O(1).

The following traverses the linked list and converts the data into a list, and then check if an array is a palindrome – which can be done several ways in O(N) time.

The overall time and space complexity is O(N).

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def solve(self, node):
        data = []
        while node:
            data.append(node.val)
            node = node.next
        return data[::-1] == data

Checking Palindrome Linked List via Using Stack

We can walk through the linked list and append the values one by one to stack, then if we walk from the begining and pop elements from the stack – they should equal if it is a palindrome list.

The time and space complexity is both O(N) – as we are using a list/stack.

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def solve(self, node):
        data = []
        head = node
        while head:
            data.append(head.val)
            head = head.next
        head = node
        while head:
            if data[-1] != head.val:
                return False
            data.pop()
            head = head.next
        return True

Reverse Second Half of Linked List

We can use the fast and slow pointer to get the middle of the linked list – then if break the linked list in the middle and reverse the second half, both linked lists should equal.

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def solve(self, node):
        fast, slow = node, node
        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next

        right = None
        while slow:
            p = slow.next
            slow.next = right
            right = slow
            slow = p

        left = node
        while left and right:
            if left.val != right.val:
                return False
            left = left.next
            right = right.next
        return True

Time complexity is O(N) and space is O(1) but we are modifying the original linked list.

Recursive Algorithm to Check Palindrome Linked Lists

Recursion is based on stack – thus we can move the head pointer after recursion, and then use this to compare the corresponding node.

# class LLNode:
#     def __init__(self, val, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def solve(self, node):
        root = node
        def dfs(node):
            if node is None:
                return True
            nonlocal root
            ans = dfs(node.next)
            if root.val != node.val:
                return False
            root = root.next
            return ans
        return dfs(node)

Time and space complexity is O(N).

See also: How to Reverse Linked List within Interval? (C/C++)

–EOF (The Ultimate Computing & Technology Blog) —