Question

Suppose a linked list of 20 nodes. The middle node has a data –250. Write the pseudocode to replace the middle node of the linked list with a new node and new data. Assume that the list's head pointer is called head_ptr and the data for the new node is called entry

Answer 1

I am explaining the approach step by step because according to me this would be the easiest way to understand the code. First of all

Step 1:- Find the node which has to be replaced

bool search(Node* head, int x)
{
Node* current = head; // Initialize current
while (current != NULL)
{
if (current->key == x) // here the current key value or the value of x is given as 250
return true;
current = current->next;
}
return false;
}
Step 2:- Now after finding the node we need to replace it with a new node and a new value so at first of this step we need to delete the node that we have found out

// Find the middle and previous of middle.
// To store previous of slow_ptr   
struct Node* prev;
while (fast_ptr != NULL
&& fast_ptr->next != NULL) {
fast_ptr = fast_ptr->next->next;
prev = slow_ptr;
slow_ptr = slow_ptr->next;
}
  
// Delete the middle node
prev->next = slow_ptr->next;
delete slow_ptr;
  
return head;
}
  

Now this will delete the required node

Step 3:- in this step now we will make a new node and a new value as 'entry' in the node

// structure of a node
struct Node {
int entry; // as said to assume in the question
Node* next;
};
  
// function to create and return a node
Node* getNode(int entry)
{
// allocating space
Node* newNode = (Node*)malloc(sizeof(Node));
  
// inserting the required data
newNode->data = entry;
newNode->next = NULL;
return newNode;
}

Step 4:- now we have to just insert the new node that we have created

// function to insert node at the middle
// of the linked list
void insertAtMid(Node** head_ptr,intx)
{
// if list is empty
if (*head_ptr == NULL)
*head_ptr =getNode(x);
else {
  
// get a new node
Node* newNode = getNode(x);
  
Node* ptr = *head_ptr;
int len = 0;
  
// calculate length of the linked list
//, i.e, the number of nodes
while (ptr != NULL) {
len++;
ptr = ptr->next;
}
  
// 'count' the number of nodes after which
// the new node is to be inserted
int count = ((len % 2) == 0) ? (len / 2) :
(len + 1) / 2;
ptr = *head_ptr;
  
// 'ptr' points to the node after which
// the new node is to be inserted
while (count-- > 1)
ptr = ptr->next;
  
// insert the 'newNode' and adjust the
// required links
newNode->next = ptr->next;
ptr->next = newNode;
}
}
  

this will add a new node with a new value in the linked list that is it will replace the value 250 of the middle node and add a new node with a value assumed to be as 'entry'.Since u asked for just pseudocode I have just provided the code of the specific operations this is not the full code. I have tried to keep my approach as simple as possible, the code I have provided I have written in my code editor and tested it.Hope my work helps u

PLEASE PUT THE THUMBS UP BUTTON IF U LIKE IT. THANK U VERY MUCH.