Как поменять местами ноды стека/односвязного списка?

В C, чтобы поменять местами ноды стека или односвязного списка, необходимо изменить ссылки на предыдущую и следующую ноду у соответствующих элементов.

Для начала, давайте определим структуру ноды:

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

Предположим, у нас есть две ноды: node1 и node2. Наша задача - поменять их местами в списке.

1. Необходимо найти предыдущие ноды для node1 и node2. Для этого мы будем проходить по списку и запоминать предыдущую ноду для каждой.

Node* prevNode1 = NULL;
Node* prevNode2 = NULL;
Node* currentNode = head;  // head - указатель на первую ноду в списке

while (currentNode != NULL) {
    if (currentNode->next == node1) {
        prevNode1 = currentNode;
    }

    if (currentNode->next == node2) {
        prevNode2 = currentNode;
    }

    currentNode = currentNode->next;
}

2. Проверяем условия и меняем ссылки на следующую ноду.

// Проверяем, являются ли ноды соседними
if (node1->next == node2) {
    if (prevNode1 != NULL) {
        prevNode1->next = node2;
    } else {
        head = node2;
    }

    node1->next = node2->next;
    node2->next = node1;
} else if (node2->next == node1) {
    if (prevNode2 != NULL) {
        prevNode2->next = node1;
    } else {
        head = node1;
    }

    node2->next = node1->next;
    node1->next = node2;
} else {
    // Ноды не соседние
    if (prevNode1 != NULL) {
        prevNode1->next = node2;
    } else {
        head = node2;
    }

    if (prevNode2 != NULL) {
        prevNode2->next = node1;
    } else {
        head = node1;
    }

    Node* temp = node1->next;
    node1->next = node2->next;
    node2->next = temp;
}

После выполнения этого кода, ноды node1 и node2 будут поменяны местами в списке.