Palindrome Linked List - Leetcode Solution

The Palindrome Linked List problem on LeetCode asks us to determine if a given singly-linked list is a palindrome. A palindrome is defined as a sequence of characters (or in this case, nodes) which reads the same backward as forward.

To solve this problem, we can use several approaches. One of the easiest methods is to reverse the second half of the linked list and then compare the first half with the reversed second half. Another method is to use a stack to store the first half of the linked list in reverse order and then compare it with the second half.

Here is a detailed solution using the first approach:

1. First, we need to determine the length of the linked list. We can do this by traversing the linked list and counting the number of nodes.

2. Next, we need to find the middle node of the linked list. We can use the fast and slow pointer method to find the middle node. The fast pointer moves two nodes at a time, while the slow pointer moves one node at a time. When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.

3. We can then reverse the second half of the linked list. To do this, we need to split the linked list into two separate lists at the middle node. We can do this by setting the next pointer of the node before the middle node to null.

4. We can then reverse the second half of the linked list using the iterative method. We need to have three pointers: prev, current, and next. We set prev to null, current to the head of the second half, and next to the next node of current. We then iterate through the second half, setting the next pointer of the current node to prev, and moving each pointer one node at a time.

5. We can then compare the first half with the reversed second half. We can use two pointers, one starting from the head of the first half, and the other starting from the head of the reversed second half. We iterate through both halves, comparing each node one at a time. If at any point we find that two nodes are not equal, we can return false, since the linked list is not a palindrome. If we reach the end of both halves and all nodes are equal, we can return true, since the linked list is a palindrome.

Here is the Python code for the solution:

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        if not head or not head.next:
            return True
        
        # Find length of the linked list
        length = 0
        node = head
        while node:
            length += 1
            node = node.next
        
        # Find middle node
        middle = length // 2
        slow = head
        fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        
        # Reverse second half of the linked list
        prev = None
        current = slow.next
        while current:
            next = current.next
            current.next = prev
            prev = current
            current = next
        slow.next = prev
        
        # Compare first half with reversed second half
        node1 = head
        node2 = prev
        while node1 and node2:
            if node1.val != node2.val:
                return False
            node1 = node1.next
            node2 = node2.next
        
        return True

The time complexity of this solution is O(n), where n is the length of the linked list, since we only need to traverse the linked list once. The space complexity is O(1), since we only need to use a constant amount of extra space to store pointers.

1