CareerCup

Use two pointers. Initalize both pointers to the front of the list then use a loop to traverse one pointer Nth times. Then moves both pointers until one reaches the end of the list. The second pointer is Nth to last element

Here n is the distance from the last element. Is there a better solution out there ??


node *getNthToLast(node *head, int *pos, int n) {
if(head==NULL) {
*pos=0;
return NULL;
}

node *nElemNode = getNthToLast(head->next, pos, n);
if((*pos)++==n)
return head;
else
return nElemNode;
}

Iteration solutions are generally better than recursive solutions. Can you do it iteratively?

Well its obvious to do it iteratively if its a doubly linked list... simply traverse till the last node... now traverse back n nodes.

On the other hand if its singly linked I dont see how it can be done in an "efficient" manner (without doing something stupid like using extra memory!). You really have to first find the length of the list somehow.... a quick way could be to traverse the list 2 nodes in each iteration of the while/for loop (something I would do to find the middle element of a linked list). Dunno if this makes sense ?

Using extra memory isn't much worse than a recursive solution. Every time you add a level to your recursion, you increase the stack. Memory usage for your recursive solution is O(n) anyway.

@KHOA U may be right... i also think that 2 pointers make sense and simplifies the solution.

If the size of the list is M(compute this) and you want N, then traverse a pointer M-N-1 times.

Taking Khoa's idea further...something like this....

int findNthPos(int pos)
{
LLIST ptr1,ptr2;
ptr1=ptr2=head;
int current=pos;
while(ptr1->next)
{
current = pos;
ptr2= ptr2->next;
ptr1 = ptr2;
while(current-- >0)
{
if(ptr1!=NULL)
ptr1=ptr1->next;
}

}
return ptr2->data;
}

Khoa's solution would work fine. To put it into code

int findNthPos( LinkedList* listHead, int pos )
{
if ( pos < 0 || listHead == NULL )
return FAILURE;
LinkedList *ptr1, *ptr2;
ptr1 = ptr2 = head;
while( pos > 0 )
{
if( ptr1 == NULL )
return FAILURE; // could return some other error value
ptr1 = ptr1->next;
pos--;
}
while( ptr1 != NULL )
{
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
return ptr2->data;
}

Trying to see if i can put spaces in here ... being a Virgo, i tend to be fussy about small things sometimes :-)
int findNthPos( LinkedList* listHead, int pos)
{
&nbsp;&nbsp;&nbsp;&nbsp;if( pos < 0 || listHead == NULL )
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return FAILURE;
// look up the previous answer for complete code
}

node* findNthPos( node* head, int pos )
{
node *nth, *current;
int n = 0;
nth = listHead;
current = listHead->next;
while(current)
{

current = current->next;
if(n == pos)
{
nth = nth->next;
}
else
{
n++;
}
}
}
if(n == pos)
return nth;
else
return NULL; /* no such node */

}

node findNode(LinkedList list, int pos)
{
int size=0;
iter=list.head;
while(iter != null)
{
size++;
iter = iter -> next;
}

foundNode=list.head;
for(int i=2;i<=size-pos;i++)
{
foundNode=foundNode->next;
}

return foundNode;
}

Although the above solutions may work, such complex solutions can potentially introduce bugs that are cumbersome to detect.

Just for fun...to find the nth to last element.

If you know how many elements are in the linked list, and you have a pointer to the first element and the last element. Also, assuming that its a double-linked list.

Determine if the Nth element is closer to the front of the list, or the back of the list, ie (length/2). If its closer to the front of the list, travse from the front of the list. If its closer to the back of the list, traverse from the back.

Khoa's solution would work fine. To put it into code

node* findNthLast(node* head, int n){

if(n<0){ //check for negative input
cout<<"Error";
return NULL;
}

node *nBehind; //n-behind pointer
node *curr = head;

for(int i=0; i<n; i++){
if(curr->next){
curr = curr->next
}
else{
return NULL;
}

nBehind = head;
while(curr->next){
curr = curr->next;
nBehind = nBehind->next;
}

return nBehind;
}

Khoa's solution would work fine. To put it into code

node* findNthLast(node* head, int n){

if(n<0){ //check for negative input
cout<<"Error";
return NULL;
}

node *nBehind; //n-behind pointer
node *curr = head;

for(int i=0; i<n; i++){
if(curr->next){
curr = curr->next
}
else{
return NULL;
}
}

nBehind = head;
while(curr->next){
curr = curr->next;
nBehind = nBehind->next;
}

return nBehind;
}

What is the difference between 2 pointers solution and Jack's solution? i.e.

1. Count the number of elements. O(M) time, say M nodes totally.
2. From begining travel M-N+1 steps.

The numbers of steps are the same for both.

The 2 pointer approach will take only M steps.

I think 2 pointer approach also takes 2M-N+1 moves.

Why don you take Saloni's code and spend some time to analyze the number of steps.

Assuming that Node represents a node in the linked list.

struct ptrpos
{
Node *ptr;
int pos;
}
With array of n structures ptrpos_array, walk through the
list and fill in the array with pointer to the node
and its position till you reach the end. Now we know
the number of nodes lets say it is m. The pointer to
the nth node is at ptrpos_array[m-n+1].

This approach also takes o(m)

Forget to mention, just round robin the array
filling once you reach the end of the array.

ListNode* nthFromBack(LinkedList* list, int n)
{
int i = 1;
ListNode* node = list->first;
ListNode* to_return = NULL;
while (node)
{
if (i == n)
to_return = node;

node = node->next;
i++;
}
return to_return;
}

I'd test this with a few test cases... the edge cases (list size 0, 1), maybe a five-element list, and a case where n is greater than the list size.

ListNode* nthFromBack(LinkedList* list, int n)
{
int i = 1;
ListNode* node = list->first;
ListNode* to_return = NULL;
while (node)
{
if (i == n)
{
to_return = list->first;
}
if (i>n)
{
to_return = to_return->next ;
}

node = node->next;
i++;
}
return to_return;
}
Hi Corrected code is above.. Please check the difference

take 2 pointers...
move one N steps and then start moving the second also..when the first hits last the second is Nth from last :)

node *find(int n, node *p) {
node *temp;
int num = 0;
if (p == NULL) return -1; /* checking error condition */
if (n == 0) return p; /* another error case */
temp = p;
while (p != NULL && num < (n-1)) {
p = p->next; num++;
}
if (p == NULL) return -1; /* list is not big enough */
while (p != NULL) {
p=p->next; temp=temp->next;
}
return temp;
}

Amazing solution and smart too..

Hi guys
I think instead of using two pointers and then traversing the list we could use some extra space and do it with one pointer.
We can use a circular queue of size n+1 and then start traversing the list till end and keep inserting the elements in the queue.When we reach the end of the list the front element in the queueis the required node.

1) Take 2 pointers A and B
2) Point both to starting of list A=0 b=0
3) Move one pointer to nth node A=n-1
4) Move both the pointers and stop when A hits the last Node .Now B will point to the Nth Node from last

Khoa's solution is right and it is also mentioned in the book PIE with the same solution

void show_n_elment(link *ln, int N)
{
link *nelement = ln, *node = ln;
int i = 0 ;
while(i < N && node != NULL)
{
i++;
node = node->next;
}
if(i != N)
{
printf("\n No. of element in link list is less than %d \n ",N);
return ;
}
else
{
while(node != NULL)
{
node = node->next;
nelement = nelement->next;
}
}
printf("\n %dth element of link list from end is : %d " ,N,nelement->info);
}

Simple approach on khoa's solution

struct list
{
int data;
struct list *next;
};
typedef struct list myList;

myList * find5thNode(myList *head)
{
myList *fast = NULL;
myList *slow = NULL;
int count = 1;

fast = slow = head;

while(NULL != fast)
{
if ( (count >1) && ((count % 5) == 1)) /* 5 times slower then fast pointer*/
slow = slow->next;

fast = fast->next;
count++;
}

/* in case list contains lesser than 5 nodes, this returns NULL, which is ok as there is no 5th node in the list */
if(count <5)
return NULL;
else
return slow;
}


}

For any number n, just replace 5 with n. (count%n) does the trick, it moved slow pointer n times slower than the first one.

i dont exactly understand this...
Does this find nth from the tail?
like if we have to find rd from the tail with 10 nodes, does the code find the 7th node?

The problem is more of complexity.
One solution is to count the nodes and return the 7th (after you know that there are 10 elements), or maintain a counter as u add nodes.

The simpler solution is to run two pointers, ptr0 and ptr1, and start using ptr1 after ptr0 has reached the nth element (checking that it is not out of bounds)
Thus, when ptr1 reaches the end of the list, ptr1 points exactly to the nth from tail element.

The above solution gives n from front.
The point to note is nth from tail is difficult in a singly linked list.

I am of a different opinion.
Better use a stack. Assuming worst case where this linked list is single linked list . We do not know number of nodes we do not know the size. Just keep pushing addresses of nodes on a stack still you get end of list.
When end of list is achieved just pop n-1 nodes addresses from the stack and peek top of stack. You will get nth node from last.
Any suggestions on this approach??

I thin that stack approaching is not good in terms of memory management and we also need additional work for sorting either. as you mentioned, we do not know how big the size of liked list. but no matter what it's O(m)
iteration would be better, I mean it's simple and clear enough I think.

Reverse the list (which can be done in O(n) ) and find the nth position and again reverse the list

#include <iostream.h>
#include<iomanip.h>
#include<conio.h>
using namespace std;
struct node
{
int data;
node *nxt;// Pointer to next node
};

node *start_ptr = NULL;
node *current; // Used to move along the list

void add_node_at_end()
{ node *temp, *temp2; // Temporary pointers

// Reserve space for new node and fill it with data
temp = new node;
cout << "Please enter the data value: ";
cin >> temp->data;
temp->nxt = NULL;

// Set up link to this node
if (start_ptr == NULL)
{ start_ptr = temp;
current = start_ptr;
}
else
{ temp2 = start_ptr;
// We know this is not NULL - list not empty!
while (temp2->nxt != NULL)
{ temp2 = temp2->nxt;
// Move to next link in chain
}
temp2->nxt = temp;
}
}

void display_list()
{ node *temp;
temp = start_ptr;
cout << endl;
if (temp == NULL)
cout << "The list is empty!" << endl;
else
{ while (temp != NULL)
{ // Display details for what temp points to
cout << "Data : " << temp->data;
if (temp == current)
cout << " <-- Current node";
cout << endl;
temp = temp->nxt;

}
cout << "End of list!" << endl;
}
}

void findNthLast()
{
node *nBehind; //n-behind pointer
node *curr = start_ptr;
int n=3;
for(int i=0; i<n-1; i++)
{
if(curr->nxt)
{
curr = curr->nxt;
}
}
nBehind = start_ptr;
while(curr->nxt)
{
curr = curr->nxt;
nBehind = nBehind->nxt;
}
cout<<"The third last element is :"<<nBehind->data;
}

int main()
{
start_ptr = NULL;
char option;
do
{
display_list();
cout << endl;
add_node_at_end();
cout<<"Enter another value (y/n):";
cin>>option;
}while (option == 'y');
display_list();
cout<<"Here is the third node from the end in the list\n";
findNthLast();
getch();
}

If we don't have to maintain the list in its original form, then reverse the list as we iterate the first time. So from L, we now have L' (reversed list). Now iterate N steps in L' to reach Nth last element in original list L. This would require M+N-1 steps. However, it keeps the list in reversed state. If N is very close to M, then this approach is worse than iterating twice on L. Worst case performance of both approaches are the same. If you are going to hit the 'back' of the list, then the approach stated above would work better.

Ok

node* nth_last(node* head, int n)
{
	node* nth;
	int i;
	nth=head;
	for(i=0;i<n && nth;++i)
		nth=nth->next;
	if(!nth) return 0;
	while(nth)
	{
		nth=nth->next;
		head=head->next;
	}
	return head;
}

2-pointer approach is the best solution for this question.

All other solutions need extra time or space. Stack / Hash map approach needs extra O(n) space. Recursion (whoever suggested the reversing-approach) is equally bad. Recursion eats up a lotta stack. The function stack's size grows by twice with every recursive call.

So, stick to slow-fast pointer method which is O(n) max.

I want to solve this problem using recursion in JAVA. Can anyone please help me out?

//c#
 public Node nthToLast(int n)
        {
            Node runnerNode1 = firstNode;
            Node runnerNode2 = firstNode;

            for (int j = 0; j < n - 1; ++j)
            {
                runnerNode2 = runnerNode2.nextNode;
            }
            while (runnerNode2.nextNode != null)
            {
                runnerNode1 = runnerNode1.nextNode;
                runnerNode2 = runnerNode2.nextNode;
            }
            return runnerNode1;
        }

Solutions :
1.Two pointer Solution (move first pointer to n and then start moving both the pointer till first touches the end and now the second pointer is the nth node from end)
2.Traverse once and check the length of the list and now traverse len-n times from beginning.
3.Use Hashtable <position,data> push everything into the hasttable and pop the len_of_hash-n from the table
4.Push every data into stack and now pop up the value n times and then you will get your node.