Algorithm : Delete middle node from singly linked list

Questions about singly linked list are frequently asked during technical interviews. Today we will share with you one algorithm question about singly linked list. Here is the problem description.

Assuming the only information you are giving is there is a pointer to a middle node of a singly linked list, no other information about the linked list is given. Please delete this node and don't affect the structure of the linked list.

Initially you may think this question is easy if you know the head node of the linked list, but unfortunately we don't know what the head is and hence we cannot know the pointer where the previous node of this node is. Actually there is a tricky way to "delete" this node. instead of deleting this actual node, we just need to assign the contents of the node's next node to this node and then make this node's next node to be its next node's next node. 

Below is a sample code snippet written in C.

#include <stdio.h>

struct Node {
	struct Node* next;
	char value;
};

// Print the singlely linked list
void printList(struct Node* head){
	while (head != 0){
		printf("%c->", head->value);
		head = head->next;
	}
	printf("null\n");
}

// Remove one node from linked list
void removeNode(struct Node* node){
	if (node->next == 0){
		node->value = '0';
		node = 0;
	}
	else {
		struct Node* next = node->next;
		node->value = next->value;
		node->next = next->next;
		next = 0;
	}
}

int main(){
	struct Node* a = malloc(sizeof(struct Node));
	struct Node* b = malloc(sizeof(struct Node));
	struct Node* c = malloc(sizeof(struct Node));
	struct Node* d = malloc(sizeof(struct Node));

	a->value = 'A';
	b->value = 'B';
	c->value = 'C';
	d->value = 'D';

	a->next = b;
	b->next = c;
	c->next = d;
	d->next = 0;

	// print the original list
	printList(a);

	// remove node b
	removeNode(c);

	// print the new list
	printList(a);

	free(a);
	free(b);
	free(c);
	free(d);
}

The output of this program will be :

A->B->C->D->null
A->B->D->null