A palindrome is a sequence of characters that is read the same forward and backward. For example, “racecar” is a palindrome.

In the context of a linked list, we can consider it a palindrome if the sequence of values in the list is the same when read from left to right and from right to left.

For example, consider the following linked list:

1 -> 2 -> 3 -> 2 -> 1 -> null

This linked list is a palindrome because the sequence of values in the list is the same when read from left to right and from right to left: 1, 2, 3, 2, 1.

The goal of this problem is to check whether a given linked list is a palindrome.

1: Check Palindromic Linked List by finding Middle Node

  1. Traverse the linked list to find the middle node.
  2. Reverse the second half of the linked list.
  3. Compare the values in the first half of the linked list with the reversed values in the second half of the linked list.

If the values in both halves of the linked list match, then the linked list is a palindrome. Otherwise, it is not.

The time complexity of this approach is O(n), where n is the number of nodes in the linked list.

The space complexity is O(1), since we only need a constant amount of extra space to keep track of the middle node and to reverse the second half of the linked list.

def is_palindrome(head):
    if not head or not head.next:
        return True

    # Step 1: Find the middle node
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    # If the linked list has odd number of nodes, skip the middle node
    if fast:
        slow = slow.next

    # Step 2: Reverse the second half of the linked list
    prev = None
    curr = slow
    while curr:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next

    # Step 3: Compare the values in the first half of the linked list with the reversed values in the second half
    left = head
    right = prev
    while right:
        if left.val != right.val:
            return False
        left = left.next
        right = right.next

    return True

2: Check Palindromic Linked List using Stack

We can use a stack to store the values of the first half of the linked list. We start by traversing the linked list to find its length. We then push the first half of the values onto a stack, skipping the middle node if the list has an odd number of nodes.

See also  How to combine two column matrices in Python

We then traverse the second half of the linked list, popping values off the stack and comparing them to the values in the second half of the list. If all the values match, then the linked list is a palindrome.

def is_palindrome(head):
    if not head or not head.next:
        return True

    # Find length of the linked list
    length = 0
    curr = head
    while curr:
        length += 1
        curr = curr.next

    stack = []
    curr = head
    for i in range(length // 2):
        stack.append(curr.val)
        curr = curr.next

    # If the list has an odd number of nodes, skip the middle node
    if length % 2 != 0:
        curr = curr.next

    # Compare values in the second half of the list with the values in the stack
    while curr:
        if curr.val != stack.pop():
            return False
        curr = curr.next

    return True

3: Check Palindromic Linked List using Recursion

We can also use recursion to compare the values in the first half of the linked list with the values in the second half of the list.

We start by recursively traversing the linked list to find the middle node. We then compare the value of the middle node with the value of the node at the end of the first half of the list.

We continue this process recursively for each pair of nodes, moving toward the middle of the list. If all the pairs of nodes match, then the linked list is a palindrome.

def is_palindrome(head):
    length = get_length(head)
    result = is_palindrome_recurse(head, length)
    return result.is_palindrome

def get_length(head):
    length = 0
    curr = head
    while curr:
        length += 1
        curr = curr.next
    return length

def is_palindrome_recurse(head, length):
    if not head or length <= 0:
        return Result(head, True)
    elif length == 1:
        return Result(head.next, True)

    result = is_palindrome_recurse(head.next, length - 2)

    if not result.is_palindrome or not result.node:
        return result

    result.is_palindrome = head.val == result.node.val
    result.node = result.node.next

    return result

class Result:
    def __init__(self, node, is_palindrome):
        self.node = node
        self.is_palindrome = is_palindrome

The is_palindrome_recurse function takes in the current node and the length of the remaining list to be checked.

See also  Detect and Remove a Loop in a Linked List

It returns a Result object that contains the current node and whether or not the linked list is a palindrome.

The Result class is a simple class that contains two fields: node, which stores the current node, and is_palindrome, which is a boolean value that indicates whether the linked list is a palindrome.

The time complexity of this solution is O(n), where n is the number of nodes in the linked list. The space complexity is also O(n),

since the function call stack can have up to n/2 frames in the worst case, where n is the number of nodes in the linked list.

Which one is better and optimum

Each of the three methods for checking if a linked list is a palindrome has its own advantages and disadvantages.

The first method using the slow and fast pointers to find the middle node and reverse the second half of the linked list has a space complexity of O(1), which is the most memory efficient solution.

It also only requires a single pass through the linked list, making it faster than the first method. However, it involves modifying the original linked list, which may not be desirable in certain situations.

The second method using a stack is simple and straightforward to implement, and has a space complexity of O(n), where n is the number of nodes in the linked list.

However, it requires two passes through the linked list, which can make it slower than the other methods.

The third method using recursion is a clever way to avoid modifying the original linked list and only requires a single pass through the linked list.

See also  Introduction to Linked List

However, it has a space complexity of O(n) due to the recursive call stack, which may not be desirable in some situations.

In terms of time complexity, all three methods have a time complexity of O(n), where n is the number of nodes in the linked list.

Therefore, the choice of which method to use would depend on the specific requirements of the problem and the constraints of the system it is being implemented on.