Las estructuras de datos lineales, como las listas enlazadas y las listas secuenciales, constituyen la base para la organización de información en memoria dinámica y estática. A continuación, se detallan implementaciones optimizadas para la creación, inversión, fusión y manipulación condicional de estas estructuras utilizando C++.

Definición del Nodo y Operaciones Fundamentales

Para trabajar con listas enlazadas simples, primero definimos la estructura del nodo. Las operaciones básicas incluyen la construcicón de la lista mediante inserción por cola y el recorrido para su visualización.

#include <iostream>

struct ListNode {
    int value;
    ListNode* next;
    ListNode(int val) : value(val), next(nullptr) {}
};

// Inserción por cola (Tail Insertion)
void appendNode(ListNode*& head, int val) {
    ListNode* newNode = new ListNode(val);
    if (!head) {
        head = newNode;
        return;
    }
    ListNode* current = head;
    while (current->next) {
        current = current->next;
    }
    current->next = newNode;
}

// Recorrido e impresión
void printList(ListNode* head) {
    ListNode* current = head;
    while (current) {
        std::cout << current->value << " -> ";
        current = current->next;
    }
    std::cout << "nullptr\n";
}

// Liberación de memoria
void freeList(ListNode*& head) {
    while (head) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}

Inversión in-place y Eliminación Condicional

La inversión de una lista enlazada se realiza de manera óptima en tiempo O(n) y espacio O(1) utilizando tres punteros. Asimismo, la eliminación de nodos que cumplen una condición específica (por ejemplo, valores pares) requiere un manejo cuidadoso de los punteros para evitar pérdidas de memoria.

// Inversión iterativa de la lista
void reverseList(ListNode*& head) {
    ListNode* prev = nullptr;
    ListNode* curr = head;
    while (curr) {
        ListNode* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    head = prev;
}

// Eliminación de nodos con valores pares
void removeEvenValues(ListNode*& head) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* prev = dummy;
    ListNode* curr = head;

    while (curr) {
        if (curr->value % 2 == 0) {
            prev->next = curr->next;
            delete curr;
            curr = prev->next;
        } else {
            prev = curr;
            curr = curr->next;
        }
    }
    head = dummy->next;
    delete dummy;
}

Inserción Ordenada, Fusión y División

Mantener el orden en una lista enlazada requiere recorrer la estructura hasta encontrar la posición correcta. La fusión de dos listas ordenadas y la división de una lista en dos basadas en una condición (como paridad) son operaciones clásicas de divide y vencerás.

// Inserción manteniendo el orden ascendente
void insertSorted(ListNode*& head, int val) {
    ListNode* newNode = new ListNode(val);
    if (!head || head->value >= val) {
        newNode->next = head;
        head = newNode;
        return;
    }
    ListNode* current = head;
    while (current->next && current->next->value < val) {
        current = current->next;
    }
    newNode->next = current->next;
    current->next = newNode;
}

// Fusión de dos listas ordenadas
ListNode* mergeSortedLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;

    while (l1 && l2) {
        if (l1->value <= l2->value) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

// División de lista en impares y pares
void splitByParity(ListNode* head, ListNode*& oddHead, ListNode*& evenHead) {
    ListNode oddDummy(0), evenDummy(0);
    ListNode* oddTail = &oddDummy;
    ListNode* evenTail = &evenDummy;

    while (head) {
        if (head->value % 2 != 0) {
            oddTail->next = head;
            oddTail = oddTail->next;
        } else {
            evenTail->next = head;
            evenTail = evenTail->next;
        }
        head = head->next;
    }
    oddTail->next = nullptr;
    evenTail->next = nullptr;
    oddHead = oddDummy.next;
    evenHead = evenDummy.next;
}

Listas Secuenciales y Aplicación en Polinomios

Las listas secuenciales (arreglos) permiten acceso aleatorio, lo que facilita operaciones como la inversión mediante intercambio de extremos. Por otro lado, las listas enlazadas son ideales para representar polinomios dispersos, donde cada nodo almacena el coeficiente y el exponente.

#include <vector>
#include <algorithm>

// Inversión de lista secuencial (Array/Vector)
void reverseSequentialList(std::vector<int>& arr) {
    int left = 0;
    int right = arr.size() - 1;
    while (left < right) {
        std::swap(arr[left], arr[right]);
        left++;
        right--;
    }
}

// Estructura para Polinomios
struct PolyNode {
    int coeff;
    int exp;
    PolyNode* next;
    PolyNode(int c, int e) : coeff(c), exp(e), next(nullptr) {}
};

// Suma de dos polinomios representados como listas enlazadas
PolyNode* addPolynomials(PolyNode* p1, PolyNode* p2) {
    PolyNode dummy(0, 0);
    PolyNode* tail = &dummy;

    while (p1 && p2) {
        if (p1->exp > p2->exp) {
            tail->next = new PolyNode(p1->coeff, p1->exp);
            p1 = p1->next;
        } else if (p1->exp < p2->exp) {
            tail->next = new PolyNode(p2->coeff, p2->exp);
            p2 = p2->next;
        } else {
            int sumCoeff = p1->coeff + p2->coeff;
            if (sumCoeff != 0) {
                tail->next = new PolyNode(sumCoeff, p1->exp);
            }
            p1 = p1->next;
            p2 = p2->next;
        }
        if (tail->next) tail = tail->next;
    }
    
    while (p1) {
        tail->next = new PolyNode(p1->coeff, p1->exp);
        tail = tail->next;
        p1 = p1->next;
    }
    while (p2) {
        tail->next = new PolyNode(p2->coeff, p2->exp);
        tail = tail->next;
        p2 = p2->next;
    }
    return dummy.next;
}