Today's Question:  What are you most afraid of as a programmer?        GIVE A SHOUT

Technical Article => Programming =>  Algorithm

Algorithm : Delete middle node from singly linked list

  sonic0002      2015-10-30 05:21:25      1,428    0    0

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

C ALGORITHM LINKED LIST

  SAVE AS PDF   MARK AS READ   MARK AS IMPORTANT

Share on Facebook  Share on Twitter  Share on Google+  Share on Weibo  Share on Reddit  Share on Digg  Share on Tumblr    Delicious

  RELATED


  0 COMMENT


No comment for this article.


  WRITE ARTICLE

Hosted with love by Github

By sonic0002
A cute footer seen on JSch's website http://www.jcraft.com/jsch/examples/Shell.java.html. We geeks are not so boring sometimes.