Checking if a singly linked list[string/number] is palindromic - Part 1

What is a palindromic string or number ?

A palindromic string or number is one that reads the same when reversed from the back and compared to the original one . According to literaryterms.net literaryterms , A palindromic is defined below:

A palindrome is a type of word play in which a word or phrase spelled forward is the same word or phrase spelled backward. The word palindrome (pronounced ˈpa-lən-ˌdrōm) was invented in the early 1600s by the poet and playwright Ben Jonson, using Greek roots palin and dromos meaning “again” and “direction.”

Examples of Palindromes Words :

• Never odd or even.
• Stressed desserts
• racecar
• madam
• 012210 check literaryterms for more examples.

The above word or number when flipped , result in the same result . Now to the exciting part of this post .

the initial assumption is based on the fact that you are given a singly linked list of number , an integer to be precise and asked to check if the list was palindromic i.e. reads the same from left to right with right to left . for example you are given a list of integer number such as "0->1->2->2->1->0" and asked to check if it is palindromic which return true.

To better and clear understanding of what a linked list is , check Thamaraiselvam's article on hashnode singly linked list

Below is the data structure representation of a singly linked list in python . The same applies virtually across languages .

class LinkedList:
    def __init__(self, value):
        self.value = value
        self.next = None

To solve this question , let breakdown the problem into steps. We are going to be using a mathematical approach as this is a singly linked list and not a doubly linked list [en.wikipedia.org/wiki/Doubly_linked_list]. A mathematical approach because as we know that the list can be reversed and compared with the original half while the middle node falls either as even or odd.

1. Get the length of the input linked list.

2. Get the middle node using the length in step one divide by 2 (rounded based on language format )

3. Reverse the last half of the list

4. Compare the first half with the last half.

For Example , the list "0->1->2->2->1->0" can be broken into "0->1->2" and the reversed half will be "0->1->2" this when compared will return true . Using this as an example . The code for getting the length and middle node of the linked list are as follow:

def getLinkedListLength(head):
    count = 1
    while head is not None:
        count += 1
        head = head.next
    return count

def getMiddleNode(node, length):
    count = 1
    while count != length:
        count += 1
        node = node.next
    return node

Now to reverse a linked list , I will recommend watching a how to reverse a singly linkedlist on youtube using this link (youtube.com/watch?v=O0By4Zq0OFc&t=10s) . However this is an iterative method below :

def reverseLinkedList(node):
    prevNode = None
    currentNode = node
    while currentNode is not None:
        nextNode = node.next
        nextNode = currentNode.next
        currentNode.next = prevNode
        prevNode = currentNode
        currentNode = nextNode
    return prevNode

Following step4 the code eventually becomes this:

def linkedListPalindrome(head):
    length = getLinkedListLength(head)
    startNode = head
    middleEndNode = getMiddleNode(head, length//2)
    middleStartNode = reverseLinkedList(middleEndNode)
    middleEndNode.next = None # to break the reference to the other half 
    while startNode is not None and middleStartNode is not None:
        if startNode.value != middleStartNode.value:
            return False
        startNode = startNode.next
        middleStartNode = middleStartNode.next
    return True

Hopefully this above method has given you a first clear view of how to check if a linked list is palindromic. We are now one step down and two more to finishing this series. Thanks for taking time to read this post.