IBM Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
I think it is not possible to get -nth pointer from some node in single linked list, because you have only pointer to the next node, but no pointer to previous.
If you want -nth from there is possible to traverse list from the begin, remember n previous adresses and lineary search the list for the input node, but this is little bit complicated...
You can find out this one using distance.
1. You should know the orignal header in the linked list eg) 1
2. Form a Array with given linked element with distance
list=1->2->3->4->5
eg)
a(1)->0,a(2)->1,a(3)->2,a(3)->3,,,,
in this case we need to move forward 3
eg)2
for the backward cursor set the orginal header and set the distance as -{orginal position of newpointer}-{each node position}
as per the second example
a(1)->-4,a(2)->-3,a(3)->-2,a(3)->-1,a(4)->0
This will easy for us to figure it out.
Since when did IBM start asking such Qs. As far as I knw, it asks only some silly HR Qs.!!
Can not guarantee the (-n) part. You can try:
given ptr;
prev_pointer = (struct single_lnk_lst *) (ptr-(sizeof (struct single_lnk_lst) * 2));
if(single_lnk_lst->next == ptr) // you are lucky to get to -1, now do that n more times.
public void getelement(int p, int d){
node n = head;
int count = 0;
while(n.val != p && n != null){
if(n.sibling == null){
System.out.println("enter correct input");
System.exit(0);
}
else{
count++;
n = n.sibling;
}
}
if(d > 0){
while(n != null && (d-- > 0)){
if(n.sibling == null){
System.out.println("cant move. enter correct input");
System.exit(0);
}
else{
n = n.sibling;
}
}
System.out.println(n.val);
}
else{
int k = count+d;
if(k < 0){
System.out.println("cant move. enter correct input");
System.exit(0);
}
node res = head;
while(res != null && (k-- > 0)){
res = res.sibling;
}
System.out.println(res.val);
}
}
It is not possible to trace -N node from given node in the tree.
However if Head of the list is provided, then it is simple
1. Move one pointer N ahead from head
2. Now Move one pointer from head and another from N, one by one till Given node is found.
3. At this point, you have previous pointer pointing to -N position
This is O(n) solution
for nth node from the list its straight forward
But for -nth,instead of reversing the list and again setting it back.We can break the list and make it a circular list,find the nth last element in that circular list. And later revert back the changes
Ex:
1-2-3-4-5-6-7-8 is the linked list
return N(4,-2)
break the list at 4 and connect the next pointer of 4 to 1
now u have a list 1-2-3-4-1...
now from 1 find the 2nd last element using the mth last element algo with some modification in the termination condition
and now connect 4 back to 5
Best solution:-
There is a head node denoted by list *head.
list * returnN (list *node, int n)
{
Take 2 pointers p1 & p2, make them both point to head.
Now if n<0,
Keep forwarding one pointer p1 to right for |n| times, where |n| = abs(n)
Now forward both the pointers until p1 reaches node.
return p2.
Else if n>0,
p1 point to node.
Just keep forwarding p1 to right for n times.
return p1.
For -ve, if an extra memory is allowed, its simple. If we are calling the method with (M,N) Push the elements till Mth node onto the stack and pop the N elements then you will get the m-nth element as top of the stack.
- OP November 15, 2011