Having a problem with linked list. Need to create a method, which will replace data in list, by not creating a new element but by changing pointers. For now I have such method:

    void replaceValues(Node* head, int indexOne, int indexTwo)
 {
    Node* temporaryOne = NULL;
    Node* temporaryTwo = NULL;
    Node* temp = NULL;
    Node* current = head;
    int count = 0;
    while (current != NULL) {
        if (count == indexOne)
        {
            temporaryOne = current;
        }
        else if (count == indexTwo)
        {
            temporaryTwo = current;
        }
        count  ;
        current = current->next;
    }
    current = head;
    count = 0;
    while (current != NULL) {
        if (count == indexOne)
        {
            head = temporaryTwo;
        }
        else if (count == indexTwo)
        {
            head = temporaryOne;
        }
        count  ;
        current = current->next;
    }
}

I am sure, that exists a more simpler way, how to do it, but I don't fully understand, how it works... Thanks in advance for help.

CodePudding user response：

I assume that with "replace" you actually mean "swap"/"exchange".

Some issues:

• The argument head should be passed by reference, as one of the nodes to swap may actually be that head node, and then head should refer to the other node after the function has done its job.

• The node before temporaryOne will need its next pointer to change, so you should stop your loops one step earlier in order to have access to that node and do that.

• In some cases head may need to change, but this is certainly not always the case, so doing head = temporaryOne or head = temporaryTwo is certainly not right. In most cases you'll need to link to the swapped node from the preceding node (see previous point).

• The next pointer of the node that is swapped will also need to change, as the node that follows it will be a different one than before.

As mentioned already in comments, it is advised to split the task into removals and insertions, as the fiddling with next pointers can get confusing when you try to cover all possible cases, notably making the distinction between the case where the two nodes are adjacent and when they are not.

Here are some functions that split the work into removal, insertion and finally exchanging nodes:

Node* removeNode(Node* &head, int index) {
    // If index is out of range, no node is removed, and function returns  nullptr
    // Otherwise the extracted node is returned.
    if (head == nullptr || index < 0) return nullptr;
    Node* current = head;
    if (index == 0) {
        head = head->next;
        current->next = nullptr;
        return current;
    }
    while (--index > 0) {
        current = current->next;
        if (current == nullptr) return nullptr;
    }
    Node* temp = current->next;
    if (temp != nullptr) {
        current->next = temp->next;
        temp->next = nullptr;
    }
    return temp;
}

void insertNode(Node* &head, Node* node, int index) {
    // If index is too large, node is inserted at the end of the list
    // If index is negative, node is inserted at the head of the list
    if (index <= 0 || head == nullptr) {
        node->next = head;
        head = node;
        return;
    }
    Node* current = head;
    while (--index > 0 && current->next != nullptr) {
        current = current->next;
    }
    node->next = current->next;
    current->next = node;
}

bool exchangeNodes(Node* &head, int indexOne, int indexTwo)
{
    // Returns true when successful, false when at least one index  
    // was out of range, or the two indexes were the same
    if (head == NULL || head->next == NULL || indexOne == indexTwo || indexOne < 0) return false;
    // To ensure the right order of operations, require the first index is the lesser:
    if (indexOne > indexTwo) return exchangeNodes(head, indexTwo, indexOne);
    Node* two = removeNode(head, indexTwo);
    if (two == nullptr) return false; // out of range
    Node* one = removeNode(head, indexOne);
    insertNode(head, two, indexOne);
    insertNode(head, one, indexTwo);
    return true;
}