Checking if a linked list is a palindrome

Key takeaways:
The two pointer technique checks if a linked list is a palindrome by utilizing the properties of the list's structure without extra space for reversal.
Reversing the second half of the list in place helps compare it against the first half to determine if the list reads the same forward and backward.
Two pointers approach ensures that the comparison only requires one traversal of each half, maintaining an optimal $O(n)$ time complexity.
The space complexity is $O(1)$ as the algorithm modifies the list in place, unlike approaches that require extra storage.

What is a palindrome?

A palindrome is a sequence that reads the same forwards as it does backward. For instance, the number $112333211$ is a palindrome because it appears identical when reversed. Linked lists can also exhibit this property. A linked list is considered a palindrome if its elements maintain the same order when traversed from the head to the tail and when observed in reverse order.

Problem statement

The challenge is to determine whether a singly linked list is a palindrome. Given the head of the linked list, the goal is to implement an algorithm to check if it is a palindrome or not.

Constraints:

$1\leq$ nodes $\leq10^3$
$-10^4\leq$ nodes.data $\leq10^4$

Let’s take a look at a few examples to get a better understanding of the problem statement:

Solution

The challenge of checking if a linked list is a palindrome arises from its one-way traversal nature. Unlike arrays or strings, linked lists cannot be directly reversed or indexed. However, we can leverage the two-pointer technique to split the list into two halves. By reversing the second half in place, we can compare the two halves without requiring additional space, ensuring an optimal solution. After comparison, the original structure can be restored, making this approach efficient and non-destructive.

Here’s how the algorithm works:

Use the two-pointer technique (fast and slow pointers) to identify the midpoint of the linked list.
- The slow pointer moves one step at a time.
- The fast pointer moves two steps at a time.
- By the time the fast pointer reaches the end, the slow pointer will be in the middle.
Reverse the second half of the linked list starting from the slow pointer.
Traverse the first half (starting from the head) and the reversed second half. Compare the values at each corresponding position.
Reverse the second half again to restore the linked list to its original order (if needed).
If all values match during the comparison, the list is a palindrome; otherwise, it is not.

Let’s look at the following illustration to get a better understanding of the solution:

# Class definition for a singly linked list node
class ListNode:
    def __init__(self, data=0, next=None):
        self.data = data  
        self.next = next    
# Function to create a linked list from a list of values
def create_linked_list(values):
    if not values:
        return None 
    
    head = ListNode(values[0])  
    current = head              
    
    for data in values[1:]:
        current.next = ListNode(data)
        current = current.next        
    
    return head 
# Function to print the linked list
def print_linked_list(head):
    result = [] 
    while head:
        result.append(head.data)  
        head = head.next           
    return " -> ".join(map(str, result)) 
# Function to check if a linked list is a palindrome
def is_palindrome(head):
    # Step 1: Use two pointers (slow and fast) to find the middle of the list
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next       # Move slow pointer by 1 step
        fast = fast.next.next  # Move fast pointer by 2 steps
    # Step 2: Reverse the second half of the list
    prev = None
    while slow:
        temp = slow.next   
        slow.next = prev   
        prev = slow       
        slow = temp       
    
    # Step 3: Compare the first half with the reversed second half
    left, right = head, prev
    while right:
        # Mismatch found
        if left.data != right.data:  
            return False
        left = left.next  # Move to the next node in the first half
        right = right.next  # Move to the next node in the reversed second half
    
    # The linked list is a palindrome
    return True 
# Driver code
def main():
    lists = [[4, 7, 4, 1, 2, 3, 2, 1, 4, 7, 4], 
             [1, 2, 2, 1],                      
             [1, 2, 3],                         
             [1, 4, 7, 2, 1],                   
             [1]]                           
    for i, list in enumerate(lists, 1):
        head = create_linked_list(list)
        print(i, ".\tLinked List:", print_linked_list(head))
        print(f"\n\tIs Palindrome? {'Yes' if is_palindrome(head) else 'No'}")
        print("-" * 100)
if __name__ == "__main__":
    main()

Checking if a linked list is a palindrome

If you’re eager to learn problem-solving strategies, "Grokking the Coding Interview Patterns" explores 26 essential patterns, including the Two Pointers pattern, and applies them to various real-world coding problems.

Time complexity

The time complexity of the is_palindrome function is $O(n)$ , where $n$ is the length of the linked list. This complexity arises because the function makes three linear passes over the list. First, it identifies the middle of the list using the slow and fast pointer technique, which takes $n$ time. Then, it reverses the second half of the list in place, requiring $\frac{n}2$ , which simplifies to $n$ . Finally, it compares the nodes of the first half with the reversed second half, another $\frac{n}2$ operation. These steps together result in an overall $O(n)$ complexity.

Space complexity

The space complexity of the function is $O(1)$ , as the algorithm uses only a constant amount of extra space. Even if the list is restored to its original structure after the palindrome check, it only requires another in-place reversal, maintaining the $O(1)$ space complexity.

Practice resources for LeetCode problems

If you further want to explore the two pointers pattern and the problems it solves, here are some of the problems solved by the two pointers pattern:

Frequently asked questions

Haven’t found what you were looking for? Contact Us

What happens if the linked list has an odd number of elements?

The middle element is ignored during the comparison since it does not affect the palindrome property.

Why do we reverse only the second half of a linked list?

Reversing the second half minimizes additional space usage and allows for a straightforward comparison with the first half.

Why is finding the middle of the linked list important?

The middle marks the point where we can divide the list into two halves, enabling comparison for symmetry.

Can two pointers algorithm be applied to circular linked lists?

Yes, but modifications are needed to account for the circular structure, such as breaking the loop temporarily.

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments

Checking if a linked list is a palindrome

What is a palindrome?

Problem statement

Knowledge test

Solution

Time complexity

Space complexity

Practice resources for LeetCode problems

Frequently asked questions

What happens if the linked list has an odd number of elements?

Why do we reverse only the second half of a linked list?

Why is finding the middle of the linked list important?

Can two pointers algorithm be applied to circular linked lists?