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.