|
Given a singly link list........
Microsoft Interview Questions and Answers
(Continued from previous question...)
125. Given a singly link list........
Question:
Given a singly link list, you have to keep first M nodes and then delete next N nodes, again keep M nodes and delete next N nodes and so on. Write all test cases also. Discuss the time complexity also.
maybe an answer:
Set up 2 pointers r_start, r_end. r_start will first move M steps, then r_end moves M then N steps. Reset next values and repeat.
Node processLinkList(Node firstNode, int M, int N){
Node r_start = firstNode;
Node r_end = firstNode;
while(true)
{
int m = M, n = N;
while(m-- > 0)
{
if(r_start.Next == null)
break;
r_start = r_start.Next;
}
if(m > 0) break;
while(n-- > 0)
{
if(r_end.Next == null)
break;
r_end = r_end.Next;
}
if(n > 0) {
r_start.Next = null;
break;
}
else {
r_start.Next = r_end;
r_start = r_end;
}
}
return firstNode;
}
(Continued on next question...)
Other Interview Questions
| 