Check if a Linked List is a Palindrome

A linked list is a data structure where each node contains a value and a pointer to the next node, forming a chain-like structure. In this blog, we will solve the problem of checking whether a given linked list is a palindrome. A palindrome is a sequence that reads the same forward and backward. For example, 1 -> 2 -> 2 -> 1 is a palindrome, while 1 -> 2 -> 3 is not.

The idea is to first find the middle of the linked list and then reverse the second half of the list. After that, we will compare the nodes from the first half and the reversed second half. If all the values match, the linked list is a palindrome. This method is straightforward and does not require extra space to store values.

Steps to Check if a Linked List is a Palindrome

• Traverse the linked list to find its length. This helps in identifying the middle point.
• Use two pointers to find the middle node. Use a slow and fast pointer; the slow pointer moves one step, and the fast pointer moves two steps at a time.
• Reverse the second half of the linked list. From the middle to the end, reverse the nodes to compare them with the first half.
• Compare the nodes. Use two pointers, one starting from the head of the list and the other from the start of the reversed half. Check if the values match.
• Check all nodes. Continue the comparison until one of the pointers reaches the end of its respective half.
• Restore the original list structure (optional). Reverse the second half back to its original order if required.
• Return the result. If all values match, the linked list is a palindrome; otherwise, it is not.

Logic Building to Check if the given Linked List is Palindrome

One day, a young curious developer by the name of Emily was presented with a very interesting challenge. Her challenge was to find out whether a given linked list was a palindrome. She had been introduced to the concept of palindromes in words and numbers but was particularly interested in finding a solution for a linked list. And so she started on her way into the challenge using the most naïve approach first: the brute force way.

Do the brute force

Emily thought of doing it in an easy and simple way: to traverse the linked list, save elements into an array, and check whether the stored array is a palindrome. This seemed easy to implement.

Steps Emily followed:

• Traverse the list: Traverse the linked list and store the nodes' data in an array.
• Check palindrome: Use two pointers to check and confirm that the two ends of the array are the same, ensuring the array forms a palindrome.
• Time and space complexity:
  • Time Complexity: O(n), where n is the number of elements in the linked list. This is because Emily must traverse the list and store the data.
  • Space Complexity: O(n), due to the use of an array to hold the elements.

Python code example

1class ListNode:
2    def __init__(self, val=0, next=None):
3        self.val = val
4        self.next = next
5
6def is_palindrome(head):
7    # Step 1: Traverse the linked list and store elements in a list.
8    elements = []
9    current = head
10    while current:
11        elements.append(current.val)
12        current = current.next
13
14    # Step 2: Use two pointers to check for palindrome.
15    i, j = 0, len(elements) - 1
16    while i < j:
17        if elements[i] != elements[j]:
18            return False  # If any elements don't match, it's not a palindrome.
19        i += 1
20        j -= 1
21
22    return True  # All elements match, it's a palindrome.
23
24# Example usage:
25head = ListNode(1)
26head.next = ListNode(2)
27head.next.next = ListNode(2)
28head.next.next.next = ListNode(1)
29
30print(is_palindrome(head))  # Output: True

Discovering a more efficient approach

Emily's mentor, a seasoned developer named Jack, saw her working hard and offered some advice. He suggested a more efficient way to solve the problem without using extra space. Jack explained that by reversing the second half of the linked list in place, they could compare the two halves directly.

Optimal approach: In-place reversal

Jack showed her a fast way to do this, though. The algorithm goes like this: find the middle of the list, reverse the second half, and compare the two halves. Optionally, restore the list to its original state.

Steps Jack followed

• Find the Middle: Use the slow and fast pointer technique to find the middle of the list.
• Reverse the Second Half: Reverse the second half of the list.
• Compare the Two Halves: Compare the first half and the reversed second half.
• Restore the List: (Optional) Restore the list to its original state if needed.

Time and space complexity

• Time Complexity: O(n), where n is the number of elements in the linked list. This includes finding the middle, reversing the second half, and comparing the halves.
• Space Complexity: O(1), as only a few pointers are used, and no extra space proportional to the input size is needed.

Python code example

1class ListNode:
2    def __init__(self, val=0, next=None):
3        self.val = val
4        self.next = next
5
6def reverse_list(head):
7    prev = None
8    curr = head
9    while curr:
10        next_temp = curr.next  # Store next node
11        curr.next = prev  # Reverse current node's pointer
12        prev = curr  # Move pointers one position ahead
13        curr = next_temp
14    return prev  # Return new head after reversal
15
16def is_palindrome(head):
17    if not head or not head.next:
18        return True  # A single node or empty list is always a palindrome.
19
20    # Step 1: Find the end of the first half and reverse the second half.
21    slow = fast = head
22    while fast and fast.next:
23        slow = slow.next
24        fast = fast.next.next
25
26    second_half_start = reverse_list(slow)
27
28    # Step 2: Check whether the first half and the second half are equal.
29    p1 = head
30    p2 = second_half_start
31    result = True
32    while result and p2:
33        if p1.val != p2.val:
34            result = False  # If values are not equal, it's not a palindrome.
35        p1 = p1.next
36        p2 = p2.next
37
38    # Step 3: Restore the list and return the result.
39    reverse_list(second_half_start)  # Optional: Restore the original list
40    return result
41
42# Example usage:
43head = ListNode(1)
44head.next = ListNode(2)
45head.next.next = ListNode(2)
46head.next.next.next = ListNode(1)
47
48print(is_palindrome(head))  # Output: True

Conclusion

By comparing Emily's naive approach with Jack's efficient in-place reversal method, we see the importance of optimizing for space and time. The efficient method not only saves space but also performs well on larger lists.