Check Given Linked List is Palindrome or Not

In this class, We discuss whether Check Given Linked List is Palindrome or Not.

The reader can take a complete competitive coding course. Click Here.

Before starting competitive coding, the readers suggested completing a placement training course for basic coding. Click here.

Question:

Given a singly linked list of size N of integers.

Our Tast is to check given linked list is palindrome or not.

Example:

Input: 1-2-2-3-2-2-1-None

Output: Yes

Example 2:

Input: 1-2-5-None

Output: No

Logic:

First Way:

It is a singly linked list, so we can not move back from the last node.

Identify the mid-node of the linked list

Reverse the second half of the linked list

Check the elements present in the first and second half are the same.

If all are the same elements, then we display Yes. Otherwise No.

Finally, reverse the second half of the linked list.

Reversing a single linked list helps in many of the examples.

Second Way:

We use a recursive function call

Using a recursive function call, we move from the first to the last node.

From the last node, check the element with the first node.

We use a global variable left to start and move from the first node.

Below is the code for the first method

Code:

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

class Solution:

    def getReverse(self, head):

        curr = head

        prev = None

        next = None

        while curr != None:

            next = curr.next

            curr.next= prev

            prev = curr

            curr = next

        return prev   

    def getMid(self, head):

        fast = head.next

        slow = head

        while (fast and fast.next):

            slow = slow.next

            fast = fast.next.next

        return slow

    def isPalindrome(self, head):

        if (head.next == None):

            return True

        mid = self.getMid(head) 

        temp = mid.next

        mid.next = self.getReverse(temp)

        #compare

        head1 = head

        head2 = mid.next

        while head2 != None:

            if head1.data != head2.data:

                return False

            head2= head2.next

            head1= head1.next

        temp = mid.next

        mid.next = self.getReverse(temp)   

        return True 

n=int(input(“enter number of nodes”))

head=None

for i in range(n):

    x=int(input(“enter data”))

    ob=Node(x)

    if(i==0):

        head=ob

    else:

        tmp=head

        while(tmp.next!=None):

            tmp=tmp.next

        tmp.next=ob

ob1=Solution()

z=ob1.isPalindrome(head)

print(z)