Student Interview Question
InternsTeam: java
Country: United States
Interview Type: In-Person
Base: Create two pointers p1 and p2. Move p2 N nodes forward. ( handle situation if there are less than N nodes in list)
Step: each time save p2 into pointer p3 and try to move p2 N nodes forward.
If success, set p1 = p3 and repeat step.
If not - we moved p2 k times (k<N) and reached the end, so move p1 k times forward. node(p1) will be the answer because before this step there were N nodes between p1 and p2.
The above solutions are wrong, they are not solving the problem of finding the nth element from last.
1) Calculate the length of Linked List. Let the length be len.
2) Print the (len – n + 1)th node from the begining of the Linked List.
/* Function to get the nth node from the last of a linked list*/
void printNthFromLast(struct node* head, int n)
{
int len = 0, i;
struct node *temp = head;
// 1) count the number of nodes in Linked List
while (temp != NULL)
{
temp = temp->next;
len++;
}
// check if value of n is not more than length of the linked list
if (len < n)
return;
temp = head;
// 2) get the (n-len+1)th node from the begining
for (i = 1; i < len-n+1; i++)
temp = temp->next;
printf ("%d", temp->data);
return;
}
Hi yoyoyo, In your reply traversal is done twice. Once to find the length of list and the other to find the location. This defeats the very purpose. Question is we have to traverse the list only once. Not twice.
Recursive solution, python. since n can be of any value, you wanna also check for non positive integer.
For each node, this function returns a 3-tuple. (outcome_value, node_count_from_the_end, whether_the_job_is_done.)
So if the call to next node returns done, then the value is done and we return the result.
Otherwise, check to see if this node is the node we want by checking the node count from the end. increment count if not done.
#nth from last node of linkedlist
class Node(object):
def __init__(self, data, next):
self.data = data
self.next = next
def nth_from_last(head, n):
(value, count, done ) = nth_from_last_aux(head, n)
if not done:
return None
else:
return value
def nth_from_last_aux(head, n):
if not head:
return None
if not head.next: #last node
if n == 1:
return (head.data, None, True)
else:
return (None, 1, False)
(value, count, done) = nth_from_last(head.next, n)
if done:
return (value, count, True)
elif count+1 == n:
return (head.data, count, True)
else:
return (value, count+1, False)
#test
h = Node(1, Node(2, Node(3, Node(4, None))))
print nth_from_last(h, 2)
- Sunny February 24, 2015