Check if a Linked List is a Palindrome in C

This program demonstrates how to determine whether a singly linked list is a palindrome. A palindrome is a sequence that reads the same forward and backward. The challenge is to efficiently check this condition without converting the entire list into an array.

Program Explanation

The program is built around a linked list node structure and includes functions for adding nodes to the list, checking for palindrome properties, and displaying the list. It utilizes a fast and slow pointer technique to find the middle of the list, then reverses the second half of the list and compares it with the first half.

• struct Node: Represents each node in the linked list, containing an integer data and a pointer to the next node.
• push: Adds a new node to the front of the list.
• isPalindrome: Checks if the list is a palindrome.
• printList: Displays the content of the linked list.

Source Code

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct Node {
    int data;
    struct Node* next;
};

// Function to add a node at the front of the list
void push(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

// Function to check if the linked list is a palindrome
bool isPalindrome(struct Node* head) {
    struct Node *slow_ptr = head, *fast_ptr = head;
    struct Node *second_half, *prev_of_slow_ptr = head;
    struct Node *midnode = NULL;  // To handle odd size list
    bool result = true;  // Initialize result as true

    if (head != NULL && head->next != NULL) {
        // Get the middle of the list
        while (fast_ptr != NULL && fast_ptr->next != NULL) {
            fast_ptr = fast_ptr->next->next;
            prev_of_slow_ptr = slow_ptr;
            slow_ptr = slow_ptr->next;
        }

        // For odd sized lists, skip the middle node
        if (fast_ptr != NULL) {
            midnode = slow_ptr;
            slow_ptr = slow_ptr->next;
        }

        // Reverse the second half of the list
        second_half = slow_ptr;
        prev_of_slow_ptr->next = NULL;  // NULL terminate the first half
        struct Node* prev = NULL;
        struct Node* current = second_half;
        struct Node* next;
        while (current != NULL) {
            next = current->next;
            current->next = prev;
            prev = current;
            current = next;
        }
        second_half = prev;

        // Compare the two halves
        while (head != NULL && second_half != NULL) {
            if (head->data != second_half->data) {
                result = false;
                break;
            }
            head = head->next;
            second_half = second_half->next;
        }

        // Reconstruct the original list by reversing the second half again
        if (midnode != NULL) {
            prev_of_slow_ptr->next = midnode;
            midnode->next = prev;
        } else {
            prev_of_slow_ptr->next = prev;
        }
    }
    return result;
}

// Function to print nodes in a given linked list
void printList(struct Node* ptr) {
    while (ptr != NULL) {
        printf("%d -> ", ptr->data);
        ptr = ptr->next;
    }
    printf("NULL\\n");
}

int main() {
    struct Node* head = NULL;
    push(&head, 1);
    push(&head, 2);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);

    printf("Given linked list\\n");
    printList(head);

    if (isPalindrome(head)) {
        printf("Linked list is a palindrome.\\n");
    } else {
        printf("Linked list is not a palindrome.\\n");
    }

    return 0;
}
        

Conclusion

The provided C program checks if a linked list is a palindrome by using a fast and slow pointer technique to efficiently find the middle, reverse the second half, and then compare segments. This method minimizes space complexity by avoiding the need to convert the list into a different data structure and is efficient in terms of time complexity.