Chapter 2: Basic Abstract Data Types. Problem 2.8

Write a function to interchange the elements at position p and NEXT(p) in a singly linked list.

//program to exchange two nodes. 
//2 cases are important -- 
//If the node is the head node, in which case the head pointer needs to be adjusted.
//If the node is not the head node, it is a simple swap.

#include <iostream>
using namespace std;

struct NODE
{
    int nValue;
    NODE* next;
}; 

void CreateList(NODE** head); 
void PrintList(NODE* head); 
void ExchangeNodes(NODE** head, int nodeToExchange); 

void main()
{
    NODE* head = NULL; 
    CreateList(&head); 
    PrintList(head);
    ExchangeNodes(&head, 1); 
    PrintList(head);
    ExchangeNodes(&head, 5);
    PrintList(head);
}

void CreateList(NODE** head)
{
    if( !head )
        return;
    
    NODE* current = *head;
    for( int i = 1; i < 11; i++ )
    {
        NODE* newNode = new NODE;
        if( !newNode )
            return;
        newNode->nValue = i;
        newNode->next = NULL; 

        if( current == NULL )
        {
            //first node
            current = newNode;
            *head = current;
        }
        else
        {
            current->next = newNode;
            current = newNode;
        }
    }
}

void PrintList(NODE* head)
{
    if( !head )
        return;

    cout << "List is --> " << endl;
    for( NODE* current = head; current != NULL; current = current->next )
        cout << "[" << current->nValue << "]" << endl;
}

void ExchangeNodes(NODE** head, int nodeToExchange)
{
    if( !head )
        return;
    NODE* prev = NULL;
    NODE* curr = *head;
    for( ; curr != NULL; curr = curr->next )
    {
        if( curr->nValue == nodeToExchange )
            break;
        prev = curr;
    }

    if( !curr )
    {
        cout << "Element " << nodeToExchange << " not found." << endl;
        return;
    }
    if( curr->next == NULL )
    {
        cout << "Element " << nodeToExchange << " found but its next is NULL." << endl;
        return;
    }

    //we need to exchange
    if( prev == NULL )
    {
        //curr is the first node and we need to change the head of the list.
        NODE* temp = curr->next;
        *head = temp; //the list now starts with the second node
        prev = temp->next; 
        temp->next = curr; 
        curr->next = prev;
    }
    else
    {
        //curr is not the first node. 
        NODE* temp = curr->next->next;
        prev->next = curr->next;
        curr->next = temp;
        prev->next->next = curr;
    }
}