How to find nth element from the end of a singly linked list?

The following function is trying to find the nth to last element of a singly linked list. For example: If the elements are 8->10->5->7->2->1->5->4->10->10 then the result is 7th to last node is 7 . Can anybody help me on how this code is working or is there a better and simpler approach?

LinkedListNode nthToLast(LinkedListNode head, int n) < if (head == null || n < 1) < return null; >LinkedListNode p1 = head; LinkedListNode p2 = head; for (int j = 0; j < n - 1; ++j) < // skip n-1 steps ahead if (p2 == null) < return null; // not found since list size < n >p2 = p2.next; > while (p2.next != null) < p1 = p1.next; p2 = p2.next; >return p1; > 

Another solution may be to use recursion but it would be less effective than your algorithm. I think that your algorithm is simple and effective.

30 Answers 30

The key to this algorithm is to set two pointers p1 and p2 apart by n-1 nodes initially so we want p2 to point to the (n-1)th node from the start of the list then we move p2 till it reaches the last node of the list. Once p2 reaches end of the list p1 will be pointing to the nth node from the end of the list.

I've put the explanation inline as comments. Hope it helps:

// Function to return the nth node from the end of a linked list. // Takes the head pointer to the list and n as input // Returns the nth node from the end if one exists else returns NULL. LinkedListNode nthToLast(LinkedListNode head, int n) < // If list does not exist or if there are no elements in the list,return NULL if (head == null || n < 1) < return null; >// make pointers p1 and p2 point to the start of the list. LinkedListNode p1 = head; LinkedListNode p2 = head; // The key to this algorithm is to set p1 and p2 apart by n-1 nodes initially // so we want p2 to point to the (n-1)th node from the start of the list // then we move p2 till it reaches the last node of the list. // Once p2 reaches end of the list p1 will be pointing to the nth node // from the end of the list. // loop to move p2. for (int j = 0; j < n - 1; ++j) < // while moving p2 check if it becomes NULL, that is if it reaches the end // of the list. That would mean the list has less than n nodes, so its not // possible to find nth from last, so return NULL. if (p2 == null) < return null; >// move p2 forward. p2 = p2.next; > // at this point p2 is (n-1) nodes ahead of p1. Now keep moving both forward // till p2 reaches the last node in the list. while (p2.next != null) < p1 = p1.next; p2 = p2.next; >// at this point p2 has reached the last node in the list and p1 will be // pointing to the nth node from the last..so return it. return p1; > 

Alternatively we can set p1 and p2 apart by n nodes instead of (n-1) and then move p2 till the end of the list instead of moving till the last node:

LinkedListNode p1 = head; LinkedListNode p2 = head; for (int j = 0; j < n ; ++j) < // make then n nodes apart. if (p2 == null) < return null; >p2 = p2.next; > while (p2 != null) < // move till p2 goes past the end of the list. p1 = p1.next; p2 = p2.next; >return p1; 

Your algorithm works by first creating references to two nodes in your linked list that are N nodes apart. Thus, in your example, if N is 7, then it will set p1 to 8 and p2 to 4.

It will then advance each node reference to the next node in the list until p2 reaches the last element in the list. Again, in your example, this will be when p1 is 5 and p2 is 10. At this point, p1 is referring to the Nth to the last element in the list (by the property that they are N nodes apart).

Even if you do it in this lockstepped-fashion, isn't it analogous to iterating the list twice? We can think of each reference as an iterator, so one goes to n , and the other to n - separation . Thus, we have the same number of steps as if we used one iterator to count ( n steps) and another one to reach the node in position n - separation .

@tinchou: Your suggestion is a correct alternate implementation and perhaps a bit clearer to understand. Both implementations are O(n) so they are analagous. I would expect the implementation in Jonathan's question to be negligibly more efficient.

Is what @tinchou is suggesting recursively going to the end of the list to retrieve the size, n, then looping through again to find the k th from last element??

@franklin Yes, but I would describe it as iterating to the end of the list rather than recursing to it.

@tinchou, this lockstep approach will generally give better cache utilization, because a node hit by the front pointer may still be in cache when the rear pointer reaches it. In a language implementation using tracing garbage collection, this approach also avoids unnecessarily keeping the beginning (thus entire) list live for the duration of the operation.

What do you think regarding this approach.

1. Count length of the linkedlist.
2. Actual Node index from head = linkedlist length - given index;
3. Write a function to travesre from head and get the node at the above index.

This is good except that you traverse twice. Once to get the length of the list (because you have no other way to know the size without traversing till end) and another to actually find the element you're interested in.

//this is the recursive solution //initial call find(HEAD,k); // main function void find(struct link *temp,int k) < if( temp->next != NULL) find( temp->next, k); if((c++) == k) // c is initially declared as 1 and k is the node to find from last. coutnum

There are lots of answers here already, but they all walk the list twice (either sequentially or in parallel) or use a lot of extra storage.

You can do this while walking the list just once (plus a little bit) using constant extra space:

Node *getNthFromEnd(Node *list, int n) < if (list == null || n<1) < return null; //no such element >Node *mark1 = list, *mark2 = list, *markend = list; int pos1 = 0, pos2 = 0, posend = 0; while (markend!=null) < if ((posend-pos2)>=(n-1)) < mark1=mark2; pos1=pos2; mark2=markend; pos2=posend; >markend=markend->next; ++posend; > if (posend //mark1 and mark2 are n-1 elements apart, and the end is at least //1 element after mark2, so mark1 is at least n elements from the end while((posend - pos1) > n) < mark1 = mark1->next; ++pos1; > return mark1; > 

This version uses 2 extra pointers does less than N+n traversals, where N is the length of the list and n is the argument.

If you use M extra pointers, you can get that down to N+ceil(n/(M-1)) (and you should store them in a circular buffer)

Clever approach. My first attempt thinking about this problem was using a circular-buffer too, but from another persective.

You can just loop through the linkedlist and get the size. Once you have the size you can find the n'th term in 2n which is O(n) still.

public T nthToLast(int n) < // return null if linkedlist is empty if (head == null) return null; // declare placeholder where size of linkedlist will be stored // we are hoping that size of linkedlist is less than MAX of INT int size = 0; // This is O(n) for sure Node i = head; while (i.next != null) < size += 1; i = i.next; >// if user chose something outside the size of the linkedlist return null if (size < n) return null; // This is O(n) if n == size i = head; while(size >n) < size--; i = i.next; >// Time complexity = n + n = 2n // therefore O(n) return i.value; > 

Since this sounds like homework, I prefer to help you help yourself instead of giving an actual solution.

I suggest you run this code on some small sample dataset. Use your debugger to run lines step-by-step (you can set a breakpoint at the start of the function). This should give you an idea of how the code works.

You can also Console.WriteLine() to output variables of interest.

No you dont know the length of the linkedlist . You will have to go through once to get length of the likedlist so your approach is little in efficient;

Just another solution to this problem. Though the time complexity remains the same, this code achieves the solution in a single loop.

public Link findKthElementFromEnd(MyLinkedList linkedList, int k) < Link current = linkedList.getFirst();//current node Link currentK = linkedList.getFirst();//node at index k int counter = 0; while(current.getNext()!=null) < counter++; if(counter>=k) < currentK = currentK.getNext(); >current = current.getNext(); > //reached end return currentK; > 

this answer is flawed in the case that the k-th element from the end doesn't exist. Just notice if the length of the list is N and K>N. It could be easily solved by doing a simple check between counter and k before the return statement. :)

Just reverse the linked list in linear time and find the kth element. It still run in linear time.

I have my recursive solution at another thread in StackOverflow here

We take here two pointers pNode and qNode, both initial points to head qNode. Then, traverse till the end of list and the pNode will only traverse when there's a difference between the count and position is greater than 0 and pthNode increments once in each loop.

static ListNode nthNode(int pos) < ListNode pNode=head; ListNode qNode=head; int count =0; while(qNode!=null)< count++; if(count - pos >0) pNode=pNode.next; qNode=qNode.next; > return pNode; > 

public int nthFromLast(int n) < Node current = head; Node reference = head; for(int i=0;iwhile(reference != null) < current = current.getNext(); reference = reference.getNext(); >return current.getData(); > 

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> 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"

To understand this problem, we should do a simple analogy with a measurement example. Let's say, you have to find the place of your arm where exactly 1 meter away from your middle finger, how would you measure? You would just grab a ruler with a 1-meter length and put the top-end of that ruler to the tip of your middle-finger and the bottom-end of the meter will be exactly 1 meter away from the top of your middle-finger.

What we do in this example will be the same, we just need a frame with n-element wide and what we have to do is put the frame to the end of the list, thus the start node of the frame will be exactly n-th element to the end of the list.

This is our list assuming we have M elements in the list, and our frame with N element wide;

HEAD -> EL(1) -> EL(2) -> . -> EL(M-1) -> EL(M)

However, we only need the boundaries of the frame, thus the end boundary of the frame will exactly (N-1) elements away from the start boundary of the frame. So have to only store these boundary elements. Let's call them A and B;

HEAD -> EL(1) -> EL(2) -> . -> EL(M-1) -> EL(M) A B 

The first thing we have to do is finding B, which is the end of the frame.

ListNode b = head; int count = 1; while(count

Now b is the n-th element of the array, and a is located on the HEAD. So our frame is set, what we will do is increment both boundary nodes step by step until b reachs to the end of the list where a will be n-th-to-the-last element;

ListNode a = head; while(b.next != null) < a = a.next; b = b.next; >return a; 

public ListNode findNthToLast(int n) < if(head == null) < return null; >else < ListNodeb = head; int count = 1; while(count < n && b != null) < b = b.next; count++; >if(count == n && b!=null) < ListNodea = head; while(b.next != null) < a = a.next; b = b.next; >return a; > else < System.out.print("N(" + n + ") must be equal or smaller then the size of the list"); return null; >> > 

You can also solve the above problem using hash tables.The entries of the hash table are position of node and address of node. So if we want to find the nth node from the end(this means m-n+1 from the first where m is number of nodes).Now when we enter the hash table entries we get the number of nodes.Steps are:-

1.Traverse each node and make corresponding entries in hash table.

2.Look for the m-n+1 node in hash table we get the address.

Time complexity is O(n).

I think there is one flaw in the question code, and I wonder if its been taken from a book how is this possible. it may execute correctly but code is somewhat logically incorrect. Inside the for loop. the if condition should be checked against p2->next ! = NULL

 for (int j = 0; j < n - 1; ++j) < // skip n-1 steps ahead if (p2->next == null) < return null; // not found since list size

. rest is fine and explanation as given already the code shifts p2 (n-1) positions advance to p1 , then in while loop it move them simultaneously till p2->next reaches the end .. fell free to tell if you find my answer incorrect

The problem given in the career cup book is slightly different. It says find the nth to last element of a singly linked list.

Here is my code:

 public void findntolast(int index) < Node ptr = front; int count = 0; while(ptr!=null) < count++; if (count == index) < front = ptr; break; >ptr = ptr.next; > Node temp=front; while(temp!=null) < Console.WriteLine(temp.data); temp=temp.next; >> 

Node findKth (Node head, int count, int k) < if(head == null) return head; else < Node n =findKth(head.next,count,k); count++; if(count == k) return head; return n; >> 

can you use extra data structure .. if so it will be simple . start pushing all the nodes to a stack, maintain a counter a pop it. as per your example, 8->10->5->7->2->1->5->4->10->10 start reading the linked list and start pushing the nodes or the node->data onto a stack. so the stack will look like top->

now start popping from the top of the stack maintaining a counter=1 and every time you pop increase the counter by 1, when you reach n-th element (in your example 7th element) stop popping.

note: this will print or retrieve the data/nodes in reverse order

Here is the code using 2 pointer approach : ( source )

Slow and Faster pointer approach

struct node < int data; struct node *next; >mynode; mynode * nthNodeFrmEnd(mynode *head, int n /*pass 0 for last node*/) < mynode *ptr1,*ptr2; int count; if(!head) < return(NULL); >ptr1 = head; ptr2 = head; count = 0; while(count < n) < count++; if((ptr1=ptr1->next)==NULL) < //Length of the linked list less than n. Error. return(NULL); >> while((ptr1=ptr1->next)!=NULL) < ptr2=ptr2->next; > return(ptr2); > 

Recursion

node* findNthNode (node* head, int find, int& found) < if(!head) < found = 1; return 0; >node* retval = findNthNode(head->next, find, found); if(found==find) retval = head; found = found + 1; return retval; > 

my approach, what i think is simple and has time complexity O(n).

Step 1: First get the count of number of nodes. Run a for loop starting from first node to the last node

Step 2: Once you have the count, apply simple math, for example if we have find 7th node to the last node and the count of all nodes is 12, then (count - index)- 1 will give some kth node, upto which you will have to traverse and it will be the nth node to the last node. In this case (12 -7)-1 = 4

If the elements are 8->10->5->7->2->1->5->4->10->10 then the result is 7th to last node is 7, which is nothing but 4th node from the beginning.

In java i will use-

public class LL < Node head; int linksCount; LL()< head = new Node(); linksCount = 0; >//TRAVERSE TO INDEX public Node getNodeAt(int index) < Node temp= head; if(index >linksCount) < System.out.println("index out of bound !"); return null; >for(int i=0;i return temp.getNext(); > > 

Nobody here noticed that Jonathan's version will throw a NullPinterException if the n is larger that the length of LinkedList. Here is my version:

public Node nth(int n) < if(head == null || n < 1) return null; Node n1 = head; Node n2 = head; for(int i = 1; i < n; i++)< if(n1.next == null) return null; n1 = n1.next; >while (n1.next != null) < n1 = n1.next; n2 = n2.next; >return n2; > 

I just make little change here: when node n1 step forward, instead of checking if n1 is null, I check weather n1.next is null, or else in while loop n1.next will throw a NullPinterException.

Here is C# version of finding nth child from Linklist.

public Node GetNthLast(Node head, int n) < Node current, nth; current = nth = head; int counter = 0; while (current.next != null) < counter++; if (counter % n == 0) < for (var i = 0; i < n - 1; i++) < nth = nth.next; >> current = current.next; > var remainingCounts = counter % n; for (var i = 0; i < remainingCounts; i++) < nth = nth.next; >return nth; > 

Depending of the memory cost tolerance (O(k) in this solution) we could allocate an array of pointers of length k, and populate it with the nodes as a circular array while traversing the linked list.

When we finish traversing the linked list, the first element of the array (just be sure to calculate the 0-index properly as it's a circular array) we'll have the answer.

If the first element of the array is null, there's no solution to our problem.

First of all

As mention in comment, but to be more clear, the question is from:

It's a great book by Gayle Laakmann McDowell , a software engineer from Google, who has interviewed a lot people.

Approaches

(Assuming the linked list doesn't keep track of length), there are 2 approaches in O(n) time, and O(1) space:

• Find length first, then loop to the (len-k+1) element.
  This solution is not mentioned in the book, as I remember.
• Loop, via 2 pointer, keep them (k-1) distance.
  This solution is from the book, as the same in the question.

Code

Following is the implementation in Java , with unit test, (without using any advanced data structure in JDK itself).

KthToEnd.java

/** * Find k-th element to end of singly linked list, whose size unknown, * 
1-th is the last, 2-th is the one before last, * * @author eric * @date 1/21/19 4:41 PM */ public class KthToEnd < /** * Find the k-th to end element, by find length first. * * @param head * @param k * @return */ public static Integer kthToEndViaLen(LinkedListNodehead, int k) < int len = head.getCount(); // find length, if (len < k) return null; // not enough element, return (Integer) head.getKth(len - k).value; // get target element with its position calculated, >/** * Find the k-th to end element, via 2 pinter that has (k-1) distance. * * @param head * @param k * @return */ public static Integer kthToEndVia2Pointer(LinkedListNode head, int k) < LinkedListNodep0 = head; // begin at 0-th element, LinkedListNode p1 = head.getKth(k - 1); // begin at (k-1)-th element, while (p1.next != null) < p0 = p0.next; p1 = p1.next; >return p0.value; > static class LinkedListNode  < private T value; private LinkedListNode next; public LinkedListNode(T value) < this.value = value; >/** * Append a new node to end. * * @param value * @return new node */ public LinkedListNode append(T value) < LinkedListNode end = getEnd(); end.next = new LinkedListNode(value); return end.next; >/** * Append a range of number, range [start, end). * * @param start included, * @param end excluded, */ public void appendRangeNum(Integer start, Integer end) < KthToEnd.LinkedListNode last = getEnd(); for (int i = start; i < end; i++) < last = last.append(i); >> /** * Get end element of the linked list this node belongs to, time complexity: O(n). * * @return */ public LinkedListNode getEnd() < LinkedListNode end = this; while (end != null && end.next != null) < end = end.next; >return end; > /** * Count of element, with this as head of linked list. * * @return */ public int getCount() < LinkedListNode end = this; int count = 0; while (end != null) < count++; end = end.next; >return count; > /** * Get k-th element from beginning, k start from 0. * * @param k * @return */ public LinkedListNode getKth(int k) < LinkedListNodetarget = this; while (k-- > 0) < target = target.next; >return target; > > > 

KthToEndTest.java

(unit test, using TestNG , or you change to JUnit / . as wish)

import org.testng.Assert; import org.testng.annotations.BeforeClass; import org.testng.annotations.Test; /** * KthToEnd test. * * @author eric * @date 1/21/19 5:20 PM */ public class KthToEndTest < private int len = 10; private KthToEnd.LinkedListNodehead; @BeforeClass public void prepare() < // prepare linked list with value [0, len-1], head = new KthToEnd.LinkedListNode(0); head.appendRangeNum(1, len); >@Test public void testKthToEndViaLen() < // validate for (int i = 1; i > @Test public void testKthToEndVia2Pointer() < // validate for (int i = 1; i > > 

Tips:

• KthToEnd.LinkedListNode
  It's a simple singly linked list node implemented from scratch, it represents a linked list start from itself.
  It doesn't additionally track head / tail / length, though it has methods to do that.