Adobe Interview Question
Software EngineersCountry: India
Interview Type: In-Person
void printMthLastNode(Node head, int m){
Node *temp = head;
Node *currNode = head;
for( int i=0; i<m-1; ++i ){
temp = temp->next;
}
while(temp->next != null){
currNode = currNode->next;
temp = temp->next;
}
printf("Mth LastNode is: %d", currNode->data);
}
struct Node{
int data;
Node *next;
};
void printMthLastNode(Node head, int m){
Node *temp = head;
Node *currNode = head;
for( int i=0; i<m-1; ++i ){
temp = temp->next;
}
while(temp->next != null){
currNode = currNode->next;
temp = temp->next;
}
printf("Mth LastNode is: %d", currNode->data);
}
struct Node{
int data;
Node *next;
};
void printMthLastNode(Node head, int m){
Node *temp = head;
Node *currNode = head;
for( int i=0; i<m-1; ++i ){
temp = temp->next;
}
while(temp->next != null){
currNode = currNode->next;
temp = temp->next;
}
printf("Mth LastNode is: %d", currNode->data);
}
struct Node{
int data;
Node *next;
}
void printMthLastNode(Node head, int m)
{
Node *temp = head;
Node *currNode = head;
for( int i=0; i<m-1; ++i ){
temp = temp->next;
}
while(temp->next != null){
currNode = currNode->next;
temp = temp->next;
}
printf("Mth LastNode is: %d", currNode->data);
}
struct Node{
int data;
Node *next;
}
void printMthLastNode(Node head, int m)
{
Node *temp = head;
Node *currNode = head;
for( int i=0; i<m-1; ++i ){
temp = temp->next;
}
while(temp->next != null){
currNode = currNode->next;
temp = temp->next;
}
printf("Mth LastNode is: %d", currNode->data);
}
struct Node{
int data;
Node *next;
}
Algorithm: -
1. Take two pointers, let's say "fast" and "slow".
2. Move only fast pointer four steps from head(or root) node of linked list and slow at head of the linked list.
3. Now move both pointers simultaneously until fast reaches the end(or tail) of the linked list.
4. slow pointer here will be at m-4 position
Thanks
Hello, you can use two pointers, let's say pointer A and pointer B. Pointer B is 4 steps ahead of pointer A. When pointer B reaches the end of linked list then the pointer A points at the item 4th from the end. You don't need extra memory this way and complexity is O(n) where n is the number of nodes.
- sam October 28, 2015