Traverse through list and find if two halves match.

list.cpp

// Copyright (c) 2023 Immanuel Garcia
#include <iostream>
#include <string>
using std::string, std::cout, std::endl;

class Node {
 public:
    char data;
    Node *next;
    Node *prev;
};


// Driver for linked list


// DisplayList(Node* head)
void DisplayList(Node* head) {
    Node* current = head;  // Create a copy of HEAD since we dont want to overwrite anything by mistake here
    bool atStart = false;  // Create a variable to check if we're at the start of the list
    bool circular = false;  // Create a variable to check if the list is circular
    while (current != NULL && !circular) {  // Check to see if we've reached the end
        cout << current->data << " ";  // Print out the data stored at the current node
        current = current->next;  // Move up the list (to me this is equivalent to a index++)
        atStart = false;  // We're no longer at the start of the list
        if (!atStart) {  // If we're not at the start of the list
            if (current == head) {  // If the current node is the same as the head node
                circular = true;  // We've reached the end of the list
            }
        }
    }
    cout << endl;  // Print an endline so that the data outputted isn't jumbled up (forgot C++ a bit during summer
                        // for _reasons_ so I'm attaching `std::` to endl just to be safe
}

// InsertNodeAtEnd(Node** head, int newValue)
// This was an interesting one to create
// We want to modify the linked list that's why we use Node** instead of Node*

void InsertNodeAtEnd(Node** head, int value) {
    Node* newNode = new Node;  // We start by creating a new node (or Node, whichever sounds best)
    newNode->data = value;  // Assign it a value
    newNode->next = NULL;  // And point to no-man's land

    if (*head == NULL) {  // Check if we were given a dud
       *head = newNode;  // In this case we just promote the new node as HEAD
       return;  // Then we exit
    }
    Node* current = *head;  // If we have a valid HEAD pointer
    while (current->next != NULL) {  // We move all the way to the end of the list similar to what we'd do in the previous functions,
                                     // but in this case we're checking NEXT instead of CURRENT
       current = current->next;
    }

    current->next = newNode;  // After we reach the end we point to our new node to attach it to the list
}
// End driver for linked list

// Check if the list has a cycle using the fast/slow strategy
bool IsCircular(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast!= NULL && fast->next!= NULL) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}


// Check if the list is a palindrome
bool IsPalindrome(Node* head) {
    // Check if the chars in the linked list represent a palindrome
    // We can use the fast/slow strategy to find the middle of the list
    // Then we can reverse the second half of the list
    // Then we can compare the first half of the list to the second half
    // If they're the same, then it's a palindrome
    // If they're not, then it's not a palindrome

    Node* slow = head;
    Node* fast = head;
    while (fast!= NULL && fast->next->next!= NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
// Then we can reverse the second half of the list starting at slow which should be the middle of the list
    Node* prev = NULL;
    Node* current = slow;
    Node* next = NULL;
    while (current!= NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
// Then we can compare the first half of the list to the second half
// If they're the same, then it's a palindrome
// If they're not, then it's not a palindrome
    Node* firstHalf = head;
    Node* secondHalf = next;
    while (secondHalf!= NULL) { // We go through both lists and compare the data. When the second half is NULL, we've reached the end of the list
        if (firstHalf->data != secondHalf->data) { // If both sides dont match up at any point in time, then it is not a palindrome
            return false;
        }
        firstHalf = firstHalf->next;
        secondHalf = secondHalf->next;
    }
    return true;
}

int main() {
    string test = "ABCDCBA";  // palidrome, basically
    // Create a linked list of length 9 with each element being a random character
    Node* head = NULL;
    for (int i = 0; i <= test.length(); i++) {
        Node* newNode = new Node;
        newNode->data = test[i];
        newNode->next = NULL;
        if (head == NULL) {
            head = newNode;
        } else {
            Node* current = head;
            while (current->next!= NULL) {
                current = current->next;
            }
            current->next = newNode;
            // if (i == test.length()) {
            //    newNode->next = head;  // Make it circular
            // }
        }
    }
    // cout << "Original List: ";
    // DisplayList(head);
    cout << "Circular: " << IsCircular(head) << endl;
    cout << "Is Palindrome: " << IsPalindrome(head) << endl;
    return 0;
}