Interview Question
Country: United States
Interview Type: In-Person
/////////////////////////////////////////////////////////////////////////////
// Input: struct ListNode* list , int n
// Return: return the nth to last node or NULL if less than nth node.
/////////////////////////////////////////////////////////////////////////////
ListNode* findNthToLastLinklist(ListNode *list, int n)
{
ListNode *first = NULL;
ListNode *second = list;
// Move second pointer nth step.
while (n>0 && second)
{
second = second->next;
n--;
}
// Move both pointer now. Implicit error handle by check second.
if (second){
first = list;
while (second){
first = first->next;
second = second->next;
}
}
return first;
}
Take two pointer .initially both pointing to head or starting node.move one pointer for k-1 step and check in the middle of movement if this pointer goes to null.if null then return null. otherwise its turn to move both pointer simultaneously until second pointer next point to null.
here is the code
Node kthToLast(Node *head,int k)
{
if(*head==NULL || k<1)
{
return NULL;
}
Node *p1=head;
Node *p2=head;
for(int i=0;i<(k-1);i++)
{
if(p2==NULL)
{
return NULL
}
p2=p2->next;
}
while(p2->next!=NULL)
{
p1=p1->next;
p2=p2->next;
}
return p1;
}
Found the solution at somewhere.
Take a array of Nodes with the size k. (let say k=10)
Node[] node = new Node[10];
Node temp = head;
int count=0;
while(temp!=null){
node[count%10] = temp;
temp=temp->next;
count++
}
Now node array will have latest 10 nodes from the end. For 10th node you can fetch node[0].
(1) take 2 points i, j both point head of list.
- tomb February 17, 2012(2) Increment j to j->next for K times.
(3)After that increment both pointer by single step .
(4)When the j pointer reach j->next ==null then your i pointer points to kth element from the last