How can you get nth node from the tail in a single list (in one pass)?

Question

So, I got this question from the exam.

How can you get nth node from tail in single list?

Each node has a value and the following (which is a pointer to the next value). We are given the following:

getNodeFromTail(Node head, int x) { } 

So I did this to find the length of the list by going through it once. Then again you need to get the (length-x) node. Thus, a total of 2 workarounds.

 getNodeFromTail(Node head, int x) { int length = 0; Node headdupe = head; while (headdupe.next != NULL) { headdupe = headdupe.next; length++; } int a = length--; for (int y = 0; y < a; y++) { head = head.next; } return head; } 

That's right, but there is also a bonus question that asks if we can do the same, but only bypass it once. I could not think about it during the exam, but after I thought about one way, but I'm not too sure about it.

I could create an ArrayList of length x. Then every time I start the while loop, I add an element to the beginning of the array, cascade down and start the last element of the array. Then, when the head goes to zero, return the node to the array [x-1].

Is it correct? Is there a better solution?

Answer 1

• Make 2 pointers to the first node
• Move one pointer to x
• Move both pointers side by side until one of them on the list reaches the end.
• Your pointer further back points to the x last element.

Answer 2

I would do the following:

Keep a circular buffer of size x and add nodes to it while going through the list. When you get to the end of the list, x'th one of the tail will be equal to the next entry in the circular buffer.

In pseudo code:

 Node getNodeFromTail(Node head, int x) { // Circular buffer with current index of of iteration. int[] buffer = new int[x]; int i = 0; do { // Place the current head in its position in the buffer and increment // the head and the index, continuing if necessary. buffer[i++ % x] = head; head = head.next; } while (head.next != NULL); // If we haven't reached x nodes, return NULL, otherwise the next item in the // circular buffer holds the item from x heads ago. return (i < x) ? NULL : buffer[++i % x]; } 

This solution requires extra x in memory and is a classic example of trading runtime for memory.

Note: what to do if the input list less than x is undefined.

Answer 3

Maintain 2 pointers, Advance The first pointer to the Nth Node from the beginning Now point the second pointer to the head Continue to advance both pointers now until they reach the goal The second pointer now points to Nth from the last

Extra care in the case list has less than N items

Answer 4

You can do this without going through twice or recursing. See the following:

 int getNodeFromTail(Node head, int position) { if (head == NULL) return 0; // 2 pointers needed Node first = head; Node sec = head; for(int i = 0; i < position; i++) sec = sec.next; while (sec.next != NULL) { sec = sec.next; first = first.next; } return first; } 

Answer 5

You don't need 2 loops that are inefficient, just use 2 pointers and a counter:

 Node getNodeFromTail(Node head, int x) { Node p = head; Node q = head; int diff = 0; while (p.next != NULL) { p = p.next; if (diff >= x) q = q.next; else diff++; } return q; }