Palindrome Linked List || Python

Introduction to Palindrome Linked List:

A palindrome is a sequence of characters that reads the same forwards and backward. In the context of linked lists, a palindrome linked list is one where the elements, when read from head to tail or from tail to head, form the same sequence. For example, the linked list 1 -> 2 -> 3 -> 2 -> 1 is a palindrome because it reads the same forwards and backward.

Identifying palindrome linked lists is important in various applications such as text processing, string manipulation, and data structure analysis. It helps in determining whether a given sequence of elements exhibits symmetric properties and can have implications in algorithm design and optimization.

Problem Statement:

Given a singly-linked list, the task is to check whether the linked list is a palindrome or not. The goal is to determine if the elements in the linked list form the same sequence when read from head to tail and from tail to head.

The problem requires designing an algorithm to efficiently identify whether a linked list is a palindrome or not.

The algorithm should handle linked lists of varying lengths and return a boolean value indicating the result.

Input:

The input is a singly-linked list.

Output:

The output is a boolean value indicating whether the linked list is a palindrome.

Example: Input: 1 -> 2 -> 3 -> 2 -> 1

Output: True

Explanation:

The linked list forms a palindrome as it reads the same forwards and backwards.

Goal

The goal is to develop an algorithm that solves this problem efficiently and handles various edge cases. The algorithm should be able to handle linked lists with both even and odd numbers of nodes and identify palindromes accurately.

# 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:

        # finding the middle and end

        slow,fast=head,head
        while fast and fast.next:
            fast = fast.next.next
            slow=slow.next

        # reversing the second part of linked list

        prev = None
        while slow :
            temp = slow.next
            slow.next = prev
            prev= slow
            slow = temp 

        # Comparing the linked list two halfs

        left,right= head, prev
        while right != slow:
            if left.val != right.val:
                return False 
            left =left.next
            right = right.next
        return True

Process:

Sure! Here's the explanation for the provided code:

The code is implementing the "isPalindrome" function, which takes a linked list as input and checks whether it is a palindrome or not. The function returns a boolean value indicating the result.

The code follows the following steps:

Finding the middle and end:
- Two pointers, slow and fast, are initialized to the head of the linked list.
- The fast pointer moves two nodes at a time, and the slow pointer moves one node at a time.
- This way, when the fast pointer reaches the end of the linked list, the slow pointer will be in the middle.
Reversing the second part of the linked list:
- A "prev" variable is initialized as None to keep track of the previous node during reversal.
- Using a while loop, the second half of the linked list starting from the slow pointer is reversed.
- In each iteration, the current node's next pointer is updated to point to the previous node.
- The "prev" variable is updated to the current node, and the slow pointer is moved to the next node.
- After the loop, the "prev" variable will point to the new head of the reversed second half.
Comparing the linked list halves:
- Two pointers, "left" and "right", are initialized to the head of the original linked list and the new head of the reversed second half, respectively.
- A while loop is used to compare the values of nodes in the first half (left) with the reversed second half (right).
- If at any point the values don't match, it means the linked list is not a palindrome, and the function returns False.
- If all the values match, the function returns True.

The code efficiently determines whether a linked list is a palindrome by finding the middle, reversing the second half, and then comparing the two halves.

This approach has a time complexity of O(N), where N is the number of nodes in the linked list, and a space complexity of O(1), as it uses only a few pointers to keep track of the nodes.

Conclusion:

In conclusion, the code presented provides an efficient solution to determine whether a given linked list is a palindrome. By finding the middle of the linked list, reversing the second half, and comparing the two halves, the code effectively checks for symmetry in the values. This approach has a time complexity of O(N) and a space complexity of O(1), making it a practical solution for checking palindrome linked lists.

Happy Coding✨

DSA Blog