The question is to find the key in a linked list and if it is present then move the node containing key to the front

struct Node {
        int data;
        Node *next;
        Node(int data, Node *next_node) {
                this->data = data;
                this->next = next_node;
        }
};

void display(Node *head) {
        Node *temp_head = head;
        while(temp_head != NULL) {
                std::cout << temp_head->data << " ";
                temp_head = temp_head->next;
        }
        std::cout << '\n';
}

bool improvedSearch(Node *head, int key) {
        Node *previous = NULL, *current = head;
        while(current != NULL) {
                if(current->data == key) {
                        if(previous == NULL) {
                                return true;
                        }
                        previous->next = current->next;
                        current->next = head;
                        head = current;
                        display(head); /////
                        return true;
                }
                previous = current;
                current = current->next;
        }
        return false;
}

int main() {
        Node e(5, NULL);
        Node d(4, &e);
        Node c(3, &d);
        Node b(2, &c);
        Node a(1, &b);
        Node *head = &a;
        improvedSearch(head, 3);
        display(head); /////
        return 0;
}

When I call display inside the improvedSearch(head, 3) it shows the output "3 1 2 4 5" but when I call the display inside main function the output is "1 2 4 5". It seems like link to node containing 3 gets lost. Why is this happening?

CodePudding user response：

In improvedSearch(), you are passing in the head parameter by value, so a copy of the caller's head is made, and any new value assigned to the head parameter by improvedSearch() will be only to that copy and not reflected back to the caller. But, improvedSearch() still modifies the contents of the list, and upon exit the caller's head is still pointing at the old head node which is no longer the new head node, which is why it appears a node was lost.

To fix this, pass in the head parameter by reference instead:

bool improvedSearch(Node* &head, int key)