#linkedlist #pointers #datastructure

Question

Suppose you have a singly Linked List of n nodes and you want to insert a node in the middle of the Linked List, At least how many pointers do you need to handle to perform this task?

Answer 1

Possible Case 1 : two pointers needed.

first pointer should point to the head of the linked list, and the second pointer should point to the last node of the linked list..two pointers should move in opposite direction to find out the middle element, and at that point the new node is inserted.

Possible Case 2 : one pointer is needed.

Here we first traverse the entire linked list using only one pointer and while traversing keeping track of the count of the number of elements in the linked list.

Then we traverse half of the linked list to insert the new node.

 

correct me if i am wrong.

 

Comments

Read the question carefully.

Answer 2

Here we need to understand the meaning of “handle”. Basically in the question asked about how many pointers we have to update. Using head we can identify the index of middle, in the below example we want to insert a new node called temp between node(5) and node(6), node(5)→(node(5)’s next) will now point to node(9) and node(9)→ (node(9)’s next) will point to node(6).

So, only 2 pointers we need to handle.

 

 

Answer 3

2 pointer , the speed of first is twice as that of second one.

this will help u find the middle of link list.

hence, 2 pointers nedded.