Introduction

A Singly Linked List (LL) is a data structure where each node contains a value and a reference to the next node in the list. Given a head node reference, we want to determine whether the LL is a palindrome, meaning it reads the same forward and backward. Conventional methods for checking palindrome status involve reversing half or the entire LL, but these approaches require additional memory overhead and in-situ modifications to the LL. This article will explore a more efficient algorithm for checking LL palindromes that avoids these drawbacks.

Approaches to check for a palindrome

Prerequisite knowledge

• Array

• Singly Linked List

• Two Pointer Strategy

• Slow and Fast Pointer Strategy

Naive

One approach to check whether a Singly Linked List (LL) is a palindrome is to reverse the LL and compare it to the original LL. To do this, we traverse the LL and create a new reversed LL by inserting each node value. Then, we traverse both the original LL and the reversed LL in parallel and compare the values of each corresponding node. If all the values match, the LL is a palindrome.

This approach has a time complexity of O(n) since we must traverse the entire LL twice. It also has a space complexity of O(n) since we need to create a new reversed LL that is the same size as the original LL. However, this approach has the drawback of using additional memory for the reversed LL, which may not be optimal for large LLs or systems with limited memory resources.

Complexity: O(n) time complexity and O(n) space complexity with irrelevant memory for reversed LL.

Two Pointer Strategy

The two-pointer strategy is a technique used in programming that involves using two-pointers or variables to solve a problem. The strategy works by assigning each pointer to an element in the array and then comparing the values of the elements. Depending on the result, one or both pointers may have moved to another element in the array until the desired outcome is achieved.

Why is the two-pointer strategy unsuccessful in this particular scenario?

Instinctively speaking, the palindrome problem in an array is solved by two pointer strategy. Here, we have singly LL, which implies we can not have a second pointer pointing at the last node.

NOTE:

We could maintain the last pointer pointing at the last node of the LL. For this coding problem, we do not have the scope for that.

Even if we had the last pointer pointing at the end of the LL node, singly LL is uni-directional. So the converging phenomenon of 2 pointer strategy is missing.

If one insists on solving by the same two-pointer strategy...

1. Traverse the given LL and find the number of nodes in the given LL.

2. Take the array size based on the above calculation.

3. Traverse the linked list and copy each node's value to an array.

4. Now, we are ready to proceed with the insisted two-pointer strategy.

# Define a Node class to create individual nodes of the linked list
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

# Define a LinkedList class to create the linked list and perform operations on it
class LinkedList:
    def __init__(self):
        self.head = None

    # Method to insert a node at the end of the linked list
    def insert(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next is not None:
            last_node = last_node.next
        last_node.next = new_node

    # Method to find the number of nodes in the linked list
    def count_nodes(self):
        count = 0
        current_node = self.head
        while current_node is not None:
            count += 1
            current_node = current_node.next
        return count

    # Method to copy the values of nodes in the linked list to an array
    def copy_to_array(self, arr):
        current_node = self.head
        i = 0
        while current_node is not None:
            arr[i] = current_node.data
            i += 1
            current_node = current_node.next

# Function to check if an array is a palindrome
def is_palindrome(arr):
    n = len(arr)
    # create 2 pointers: left and right
    left = 0
    Right = n-1

    for i in range(n//2):
        if arr[left] != arr[right]:
            return False
        left+=1
        right-=1
    return True

# Example usage
llist = LinkedList()
llist.insert(1)
llist.insert(2)
llist.insert(3)
llist.insert(2)
llist.insert(1)
n = llist.count_nodes()
arr = [None] * n
llist.copy_to_array(arr)
print(arr)
print(is_palindrome(arr)) # Outputs True

Complexity: O(n) time complexity and O(n) space complexity for an auxiliary array.

We are using irrelevant memory for the array. Can we do better?

Slow and Fast Pointer Strategy

1. Find the middle element of the linked list using a slow and fast pointer.

2. The middle_node points to the middle node of the linked list.

3. Reverse the linked list from the element next to the middle element.

4. Create a temporary pointer temp that points to the beginning of the given linked list.

5. Iterate through the temp and slow pointers, comparing the values of the nodes they point to until the slow pointer reaches None.

6. Restore the reversed nodes to their original arrangement.

# Define a Node class to create individual nodes of the linked list
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

# Define a LinkedList class to create the linked list and perform operations on it
class LinkedList:
    def __init__(self):
        self.head = None

    # Method to insert a node at the end of the linked list
    def insert(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            return
        last_node = self.head
        while last_node.next is not None:
            last_node = last_node.next
        last_node.next = new_node

    # Method to find the middle node of the linked list using a slow and fast pointer
    def find_middle_node(self):
        slow_pointer = self.head
        fast_pointer = self.head
        mid_node = self.head
        while fast_pointer and fast_pointer.next:
            mid_node = slow_pointer
            slow_pointer = slow_pointer.next
            fast_pointer = fast_pointer.next.next

        # Fast pointer for odd-length LL will point to last node of LL
        # but it will point to NULL for even-length LL
        if fast_pointer:
            mid_node = slow_pointer

        return mid_node

    # Method to reverse the linked list starting from a given node
    def reverse_linked_list(self,slow_ptr):
        reverse = None
        while slow_ptr is not None:
            next = slow_ptr.next
            slow_ptr.next = reverse
            reverse = slow_ptr
            slow_ptr = next
        return reverse

    # Method to check if a linked list is a palindrome
    def is_palindrome(self):
        # Find the middle node of the linked list
        middle_node = self.find_middle_node()

        # Reverse the linked list starting from the element next to the middle element
        middle_node.next = self.reverse_linked_list(middle_node.next)

        # Iterate through the 2 half sized LL and compare values of the nodes pointed to by slow and temp pointers
        temp = self.head
        slow = middle_node.next

        while slow is not None:
            if temp.data != slow.data:
                return False
            temp = temp.next
            slow = slow.next

        # Restore the reversed nodes to their original arrangement
        middle_node.next = self.reverse_linked_list(middle_node.next)

        return True

    # Method to print LL
    def print_llist(self):
        if self.head is None:
            print("Linked List is empty")
            return
        current_node = self.head
        while current_node is not None:
            print(current_node.data, "-->", end=" ")
            current_node = current_node.next
        print("NULL")

# Example usage
llist = LinkedList()
llist.insert(1)
llist.insert(2)
llist.insert(3)
llist.insert(3)
llist.insert(2)
llist.insert(1)
print("Initial LL\n")
llist.print_llist()
print(llist.is_palindrome()) # Outputs Result
print("After LL\n")
llist.print_llist()

Source

Complexity: O(n) time complexity and improved space complexity of O(1).

Temporarily, we modified the input LL.

Exploring the constraints of node values in algorithm development

The constraints for this problem state that the values stored in each node of the linked list are 0 <= Node.val <= 9. Can we use it anyhow? This constraint can be used to our advantage in designing an efficient algorithm for determining whether the LL is a palindrome. We'll require a constructive approach initially, followed by a disruptive one towards the end.

Let's try + and -

• If the length of LL is even, process all the nodes.

• If the length of LL is odd, skip the middle node.

• Initially, sum=0

• Add the values of nodes up to the middle of the LL. Subtract the values of nodes after the middle. If the sum=0 at the end, then it's a palindrome.

This approach considers the string 1->2->3->2->1 a valid palindrome.

Unfortunately, 1->2->3->1->2 is also considered as a palindrome, which is incorrect.

Let's try * and /

• If the length of LL is even, process all the nodes.

• If the length of LL is odd, skip the middle node.

• Initially, product=0

• Multiply up to the middle of the LL and divide after the middle of the LL. If the result is one at the end, it's a palindrome.

This approach considers the string 1->2->6->3->6->2->1 a valid palindrome.

Unfortunately, 1->2->6->3->4->3->1 is also considered as a palindrome, which is incorrect.

LIMITATION:

Here, we can not use 0 as a multiplier or divisor.

Create a decimal number using LL node values.

We desire an initial constructive approach followed by a gradual disruption. So:

1. If the length of LL is even, process all the nodes.

2. If the length of LL is odd, skip the middle node.

3. Initially, decNum=0

4. Up to the middle of the LL, multiply each node value by ten and add it to the decNum.

5. From the middle of the LL, extract the unit place value using the modulo operator (%) and compare it with the slow pointer.

6. If both are matching, proceed.

7. Else, not a palindrome.

def isPalindrome(self, head):
        """
        :type head: ListNode
        :rtype: bool
        """
        # first find middle node of LL
        slow=head
        fast=head

        # get decimal representation of half the LL
        decimalNum=0

        while fast and fast.next:
            decimalNum = decimalNum*10 + slow.val
            fast = fast.next.next
            slow=slow.next

        # If fast implies LL is of odd length
        if fast:
            slow=slow.next

        # while moving slow ahead, check last digit of decimalNum
        while slow :
            if slow.val != decimalNum%10:
                return False
            decimalNum //= 10
            slow=slow.next

        return True

Complexity: Time complexity is O(n) and Space complexity is O(1)

Conclusion

To conclude, palindromes in a singly linked list can be detected using various approaches. The decimal number approach offers an optimal solution with a time complexity of O(n) and space complexity of O(1). It performs better than the naïve approach and the two-pointer strategy, which require additional memory. Unlike the slow-fast pointer strategy with a partial reversal, it does not modify the input LL.