Search for "Nth node from the end" of a linked list

Question

This seems to return the correct answer, but I'm not sure if this is really the best way to do things. It seems like I visit the first n nodes too many times. Any suggestions? Please note that I have to do this with a separate 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 this without visiting the nodes twice:

Create an empty array of size n, a pointer to this array starting at index 0, and start the iteration from the beginning of the linked list. Each time you visit a node, store it in the current index of the array and move the pointer to the array. When you fill an array, wrap and overwrite previously saved items. When you get to the end of the list, the pointer will point to the n element from the end of the list.

But it is also just an O (n) algorithm. What you are doing now is wonderful. I see no good reason for changing it.

Answer 2

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

EDIT . Yes, this is almost the same code as in the question. But I feel the pseudo code makes it clearer. To answer the question, there is no other way out, since the first N elements must be visited twice. If N small, it does not matter. If N large, then the second cycle will be small. Thus, it is always a solution to O(n) .

Answer 3

Maintain 2 pointers on nodes. When the first pointer reaches the tail, the second pointer will point to the desired node.

the 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 use the static variable 'i', which will increase while returning from the end of the list. As in, we will mainly track the Nth element starting at the end of the 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

Use two pointers pTemp and NthNode. Initially, both points point to a list node. NthNode starts moving only after pTemp has completed n moves. From both moves forward until pTemp reaches the end of the list. As a result, NthNode points to the 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 simplified in Java"

Answer 6

Your runtime is still O (n), so I don't see a problem with it.

Conceptually, you can divide the list into two parts: the part before the node that you are returning, and the part after. One of these parts will have to go through twice. Your implementation has chosen the first, advantageously without the use of additional memory (except for a pair of temporary variables).

Alternatively, you can create a stack, go through the list and put each item on the stack, and then delete n items. Then you will go to the end of the list twice, and not at 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 from the bottom of the stack when new ones are added, then you use enough space to store n nodes.)

I assume that you cannot deflate the list by reversing it. Then it is read-only memory, still O (n), still running at the end of the list twice.

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

You can use a doubly linked list, which is a linked list that also stores the address of this parent. Transversal is much simpler, as you can start at the end and begin your journey to the beginning.

Answer 9

First, count the number of nodes in the list. Then go again, counting n less nodes. However, the O (n) algorithm, which is inevitable.

Answer 10

its very simple .. take two pointers p1, p2 start p2 after p1 has moved the "n" nodes and let p1 move to the last. the node pointed to by p2 will be the nth node from the last

Answer 11

This code seems more understandable.

 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; }