Palindrome Linked List - C Solution

1. Introduction

This blog post discusses a common problem in data structures using C programming: determining if a singly linked list is a palindrome. A palindrome is a sequence that reads the same backward as forward. This problem is significant for understanding linked list operations and the concept of palindromes in data structures.

Problem

The challenge is to determine whether a given singly linked list is a palindrome. A list is a palindrome if the sequence of values in the list is the same forward and backward. This problem tests our ability to manipulate and traverse linked lists.

2. Solution Steps

1. Find the middle of the linked list using the fast and slow pointer approach.

2. Reverse the second half of the list.

3. Compare the first half with the reversed second half.

4. Return true if they are identical, false otherwise.

3. Code Program

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

// Definition for singly-linked list.
struct ListNode {
    int val;
    struct ListNode *next;
};

// Function to reverse a linked list from the given node
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL, *current = head, *next = NULL;
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

// Function to check if the linked list is a palindrome
int isPalindrome(struct ListNode* head) {
    if (head == NULL || head->next == NULL) return 1;

    // Find the middle of the list
    struct ListNode *slow = head, *fast = head;
    while (fast->next != NULL && fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // Reverse the second half of the list
    slow->next = reverseList(slow->next);

    // Compare the two halves
    struct ListNode *firstHalf = head;
    struct ListNode *secondHalf = slow->next;
    while (secondHalf != NULL) {
        if (firstHalf->val != secondHalf->val) return 0; // Not a palindrome
        firstHalf = firstHalf->next;
        secondHalf = secondHalf->next;
    }

    // Restore the list (optional)
    slow->next = reverseList(slow->next);

    return 1; // List is a palindrome
}

// Utility function to create a new node
struct ListNode* newNode(int val) {
    struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

// Main function to demonstrate isPalindrome function
int main() {
    // Create a sample list: 1->2->2->1
    struct ListNode* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(2);
    head->next->next->next = newNode(1);

    int result = isPalindrome(head); // Call the function
    printf("Output: %d\n", result); // Print the result (1 for true, 0 for false)

    // Free the list
    while (head != NULL) {
        struct ListNode* temp = head;
        head = head->next;
        free(temp);
    }

    return 0;
}

Output:

1

Explanation:

The program begins by finding the middle of the linked list using the fast and slow pointer technique. Once the middle is found, the second half of the list is reversed. 

Then, the first half and the reversed second half are compared node by node. If all corresponding nodes are equal, the list is a palindrome. 

In the example, the list 1->2->2->1 is checked and found to be a palindrome, so the output is 1 (true). 

This problem demonstrates a classic use case of linked list manipulation, particularly in splitting, reversing, and comparing linked list segments.