Finding the "Nth node from the end" of a linked list

Question

This seems to be returning the correct answer, but I'm not sure if this is really the best way to go about things. It seems like I'm visiting the first n nodes too many times. Any suggestions? Note that I have to do this with a singly linked list.

Node *findNodeFromLast( Node *head, int n )
{
    Node *currentNode;
    Node *behindCurrent;
    currentNode = head;
    for( int i = 0; i < n; i++ ) {
        if( currentNode->next ) {
            currentNode = currentNode->next;
        } else {
            return NULL;
        }
    }

    behindCurrent = head;
    while( currentNode->next ) {
        currentNode = currentNode->next;
        behindCurrent = behindCurrent->next;
    }

    return behindCurrent;
}

Answer 1

Another way to do it without visiting nodes twice is as follows:

Create an empty array of size n, a pointer into this array starting at index 0, and start iterating from the beginning of the linked list. Every time you visit a node store it in the current index of the array and advance the array pointer. When you fill the array, wrap around and overwrite the elements you stored before. When you reach the end of the list, the pointer will be pointing at the element n from the end of the list.

But this also is just an O(n) algorithm. What you are currently doing is fine. I see no compelling reason to change it.

Answer 2

Start an two pointers. Move the first one N elements ahead and then move each pointer 1 element. When the first pointer reaches the end, second pointer will give the answer.

EDIT : Yes, it is pretty much the same code as given in the question. But I feel the pseudo code make it clearer. To answer the question, there is no other go as first N elements have to be visited twice. If N is small it doesn't matter. If N is large then the second loop will be small. So it is always an O(n) solution.

Answer 3

Maintain 2 pointers n nodes apart. When the 1st pointer reaches the tail, the second pointer will be pointing to the desired node.

Code:

typedef struct _node //define the list node
{
    int i;
    struct _node *next;
}    Node;



Node * findNode(Node *listHead, int n)
{
     Node *ptr1, *ptr2;  // we need 2 pointers
     ptr1 = ptr2 = listHead; // set the pointers to point to the list head initially

    while(ptr1->next != NULL) // keep looping until we reach the tail (next will be NULL for the last node)
    {
        if(n > 0)
        {
            ptr1 = ptr1->next; //increment only the 1st pointer
            n--;
        }
        else
        {
            ptr1 = ptr1->next; //increment both pointers
            ptr2 = ptr2->next;
        }
   }
   return ptr2;    //now return the ptr2 which points to the nth node from the tail

}

Answer 4

I am using a static variable 'i' which will be incremented while backtracking from the end of the List. Like in the problem statement, we would basically tracking the Nth element starting from the end of linked list. Recursion helps us track from the end.

static int i;
public static void NthToLast(LinkedListNode head, int n)
{
    if (head == null)
        return;

    NthToLast(head.Next, n);
    i++;
    if (n == i) 
     { 
     Console.WriteLine("Mth to last" + head.Data); 
     return; 
     }

}

Answer 5

Your running time is still O(n), so I don't see that there's any problem with it.

Conceptually, you can divide the list into two parts: the part before the node you're returning, and the part after. One of these parts will have to be walked twice. Your implementation has chosen the first, at the advantage of no extra memory use (other than a couple temporary variables).

Alternatively, you could create a stack, walk the list and put each element into the stack, and then pop off n items. Then you'd be walking the end of the list twice, instead of the beginning. This has the disadvantage of storing the list in memory twice. (You could make the stack a little smarter by only storing n elements and dropping them off the bottom of the stack as new ones are added; then you're only using enough space to store n Nodes.)

I'm assuming that you can't blow away the list by reversing it in place. Then it's constant memory, still O(n), still walking the end of the list twice.

Answer 6

Use two pointer pTemp and NthNode. Initially, both points to head node of the list. NthNode starts moving only after pTemp made n moves. From the both moves forward until pTemp reaches end of the list. As a result NthNode points to nth node from the end of the linked list.

public ListNode NthNodeFromEnd(int n){
        ListNode pTemp = head, NthNode = null;
       for(int count=1; count<n;count++){
         if(pTemp!=null){
           pTemp = pTemp.getNext();
         }
       }
       while(pTemp!=null){
         if(NthNode==null){
             NthNode = head;
         }
         else{
            NthNode = NthNode.getNext();
         }
         pTemp = pTemp.getNext();
       }
       if(NthNode!=null){
         NthNode = NthNode.getNext();
         return NthNode;
       }
    return null;
  }

Refer TextBook : "Data Structure and Algorithms Made Easy in Java"

Answer 7

    Node* fetchNNodeFrmLast(int arg)
    {
    Node *temp = head;
    Node *nNode = head;
    if(head == NULL || arg <= 0)
    {
        Printf("Either head is null or invalid number entered");
        return;
    }   


    while(temp != NULL)
    {

        temp = temp->next;
        if(arg > 1)
        {
            arg--;

            continue;   
        }       
        nNode = nNode->next;    
    }

    return nNode;   
}

Answer 8

This code seems to be more clear.

public Node<T> findNthNodeFromLast(int n) {
    Node<T> current = head;
    Node<T> findElement = head;
    int length = 0;
    while (current != null && current.next != null) {
        length++;
        if (length >= n) {
            findElement = findElement.next;
        }
        current = current.next;
    }

    return findElement;
}

Answer 9

You could use a doubly linked list, which is a linked list that also stores the address of it's parent. Transversal is much easier, since you can start at the end and work your way to the beginning.

Answer 10

First count the number of nodes in the list. Then traverse again, counting off n less nodes. Still an O(n) algorithm, that's unavoidable.

Answer 11

its very simple.. take two pointers p1,p2 start p2 after p1 has travelled 'n' nodes and let p1 travel upto last.the node pointed by p2 will be nth node from last