Palindrome Linked List

Clarify the problem:

• The problem requires determining whether a given linked list is a palindrome or not.
• We need to implement a function that takes the head of a linked list as input and returns True if the linked list is a palindrome, and False otherwise.

Analyze the problem:

• Input: The head of a linked list.
• Output: A boolean value indicating whether the linked list is a palindrome or not.
• Constraints:
  • The number of nodes in the linked list can be in the range [0, 10^5].
  • The values of the nodes can be any valid integer.

Design an algorithm:

• To determine if a linked list is a palindrome, we can use the following steps:
  1. Find the middle node of the linked list using the slow and fast pointer technique.
  2. Reverse the second half of the linked list.
  3. Compare the first half of the original linked list with the reversed second half.
  4. If all the elements match, the linked list is a palindrome. Otherwise, it is not.

Explain your approach:

• We will implement a function called isPalindrome that takes the head of a linked list as input.
• We will use the slow and fast pointer technique to find the middle node of the linked list.
• Once we find the middle node, we will reverse the second half of the linked list.
• Finally, we will compare the first half of the original linked list with the reversed second half to determine if the linked list is a palindrome or not.

Write clean and readable code:

python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def isPalindrome(head):
    if head is None or head.next is None:
        return True

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

    # Reverse the second half of the linked list
    second_half = reverseLinkedList(slow.next)
    first_half = head

    # Compare the first half with the reversed second half
    while second_half:
        if first_half.val != second_half.val:
            return False
        first_half = first_half.next
        second_half = second_half.next

    return True

def reverseLinkedList(head):
    prev = None
    current = head

    while current:
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node

    return prev

Test your code:

python

# Test case 1
# Linked list: 1 -> 2 -> 3 -> 2 -> 1
# It is a palindrome.
node4 = ListNode(1)
node3 = ListNode(2, node4)
node2 = ListNode(3, node3)
node1 = ListNode(2, node2)
head = ListNode(1, node1)
assert isPalindrome(head) == True

# Test case 2
# Linked list: 1 -> 2 -> 3 -> 4 -> 5
# It is not a palindrome.
node5 = ListNode(5)
node4 = ListNode(4, node5)
node3 = ListNode(3, node4)
node2 = ListNode(2, node3)
head = ListNode(1, node2)
assert isPalindrome(head) == False

# Test case 3
# Linked list: 1 -> 2
# It is not a palindrome.
node2 = ListNode(2)
head = ListNode(1, node2)
assert isPalindrome(head) == False

# Test case 4
# Linked list: 1
# It is a palindrome.
head = ListNode(1)
assert isPalindrome(head) == True

Optimize if necessary:

• The provided solution has a time complexity of O(n) since we iterate through the linked list once.
• The space complexity is O(1) since we do the reversal in-place without using any extra space.

Handle error cases:

• The given code assumes that the input head is a valid linked list. If the input is not a valid linked list or contains invalid values, it may result in unexpected behavior.

Discuss complexity analysis:

• The time complexity of the solution is O(n), where n is the length of the linked list. We iterate through the linked list once to find the middle node and reverse the second half.
• The space complexity is O(1) since we perform the reversal in-place without using any extra space.