CareerCup

Simple answer: Not Possible
without traversing the nodes/one step.

- Anonymous September 02, 2009 | Flag Reply

'n' = node to be inserted
'p' = node after which it has to be inserted

n-> next = p->next;
p-> next = n;

- Anonymous September 02, 2009 | Flag Reply

@Anonymous How would you reach 'p' without traversing?

- Gaurav September 03, 2009 | Flag Reply

@Anonymous:
How to get to the 'p' node?
Agreed @Gaurav !

- LLOLer September 03, 2009 | Flag Reply

2nd Anonymous and pk: both of you guys send your answers along with the question to Amazon guys they'll be more than happy to hire you two knowing you have solved the problem them might be trying to solve since the inception of the company itself! rather publish a paper on it with the title something like " How to access any element of a linked list in const time, O(1) similar to an array".

- Jenny September 03, 2009 | Flag Reply

maybe this question was not DS question at all ;) ;)... the interviewer probably wanted to ask "in 1 line of code how will you add an element in the middle of linked list (in Java)?"

algorithmically not possible in 1 step (O(1)).

- singh.nikhil September 03, 2009 | Flag Reply

I think it's possible. But of course it is not for normal link but for a link with head pointer as well as middle pointer. Everytime you update the list you keep the middle pointer updated as well. Not sure if they will like this answer or not...

- lei September 03, 2009 | Flag Reply

@lei: U r rite... alongwith a header we can have 1 more pointer that points to the middle node(midptr)...(Assuming the list is a Doubly-linked list) If insertion is allowed only at the middle of the list then our ans is right since "midptr" will always point to the middle of the list... but if other type of insertionsare also allowed then we have a problem which is updating midptr everytime we insert a node into the list in an efficient way !!! Using burte force: we can have a variable that keeps track of the no of nodes. so if we hav to insert a node at the middle...we divide the counter by 2..and then traverse the list corresponding to that no and then do teh insertion... {{{but we need to improve this... just observe the pattern... initaly when thr are 2 nodes,..midptr points to 1st node. 3 nodes, midptr-->2nd node 4 nodes, midptr-->2nd node 5 nodes, midptr-->3rd node 6 nodes, midptr-->3rd node 7 nodes, midptr-->4th node so we can conclude that if the no of nodes (after inserting the node) is odd midptr points to next node. and if this no is even midptr points to same node to which it was initially pointing to. (Note this works well only if insertion r allowed only at the rear end..if we insertion r done at the front end then we need change the above soltn lttle bit)... hope this is right one.. Pls Correct me if i am wrong...!!! - codemonk September 03, 2009 | Flag Reply

I guess we need to clarify what "middle" means here.
1. Anywhere in the list?
2. The exact middle position of the list?

If 1, just add it after the head node, one step
If 2, I do not see a good solution unless the pointer to the middle point is maintained all the time.

- majun8cn September 03, 2009 | Flag Reply

I normally don't say this but I hope all you smart guys above were joking and not serious... Especially the belivers of "middle" pointer theory...

Here's my take. Since interviewer only said "linked list" without specifying / constraining the type of list (doubly linked, singly linked....etc.), I choose to use a Circular linked list.

Add the item right at the head. I'd then argue my way into convincing him that its in the "middle" of the list.

- Nix September 04, 2009 | Flag Reply

I think it is not possible to do so in a single step i.e O(1). Had it been mentioned that insertion is allowed at the middle of the list then the last two proposals might have worked, but I'm afraid as we don't have such assumptions given in the question. BTW, the idea of circular list is good to fool around the interviewer as the Qs is kinda vague.

- dabur September 04, 2009 | Flag Reply

I guess this question is about to find middle point of linked list without traversal whole linked list. Solution: 2 pointer, the first one go 1 step each time, the other go 2 step each until the end, the first pointer position is middle.

- Anonymous September 09, 2009 | Flag Reply

use an additional pointer *mid and also maintain the length of the linklist while inserting to the linklist

for every insertion insert at the mid pointer and increment the length. if the new length is odd then increment mid=mid->next.

this way the mid will always point to the middle of the linklist.

- fragzilla March 08, 2010 | Flag Reply

Are we assuming, that it is a NORMAL Linked List?

- becga March 13, 2010 | Flag Reply

It is not a single step but is not an iterative traversal, in a call k should be 1 

  public static int AddInMid(Elem node,int k) {
            int count = 0;
            if (node != null)
            {
                count = AddInMid(node.next, k+1)+1;
                if (count==k+1||count==k) {
                    Elem el = node.next;
                    node.next = new Elem();
                    node.next.next = el;
                }
            }
                return count;
        }

- dijana June 11, 2020 | Flag Reply