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

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).

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 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.
  cout<<temp->num<<' ';
}

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

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<n) {
        return null; //not enough elements in the list
    }

    //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)

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

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;i<n;i++){
	    reference=reference.getNext();
	}
	while(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<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"

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)

<-- Frame -->

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 <- N-Element Wide-> B

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

ListNode<T> b = head;
int count = 1;

while(count < n && b != null) {
	b = b.next;
	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<T> a = head;

while(b.next != null) {
	a = a.next;
	b = b.next;
}

return a;

To gather up everything, and with the HEAD checks, N < M (where M is the size of the list) checks and other stuff, here is the complete solution method;

public ListNode<T> findNthToLast(int n) {
	if(head == null) {
		return null;
	} else {
		ListNode<T> b = head;
		int count = 1;
		
		while(count < n && b != null) {
			b = b.next;
			count++;
		}
		
		if(count == n && b!=null) {
			ListNode<T> a = 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;
		}
	}
}

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

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

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).

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

Recursive solution:

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->{10, 10,4, 5, 1, 2, 7, 5, 10, 8}<-bottom.

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<index && (temp.getNext() != null);i++){
		temp = temp.getNext();
	}
	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:
><Cracking the coding interview 6th> | IX Interview Questions | 2. Linked Lists | Question 2.2.

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,
 * <p>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(LinkedListNode<Integer> head, 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<Integer> head, int k) {
        LinkedListNode<Integer> p0 = head; // begin at 0-th element,
        LinkedListNode<Integer> 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<T> {
        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) {
            LinkedListNode<T> target = 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.LinkedListNode<Integer> head;

    @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 <= len; i++) {
            Assert.assertEquals(KthToEnd.kthToEndViaLen(head, i).intValue(), len - i);
        }
    }

    @Test
    public void testKthToEndVia2Pointer() {
        // validate
        for (int i = 1; i <= len; i++) {
            Assert.assertEquals(KthToEnd.kthToEndVia2Pointer(head, i).intValue(), len - 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.

Solution in C#. Create a LinkedList with dummy values.

  LinkedList<int> ll = new LinkedList<int>();
            ll.AddFirst(10);
            ll.AddLast(12);
            ll.AddLast(2);
            ll.AddLast(8);
            ll.AddLast(9);
            ll.AddLast(22);
            ll.AddLast(17);
            ll.AddLast(19);
            ll.AddLast(20);

Create 2 pointers p1 & p1 which point to the First Node.

        private static bool ReturnKthElement(LinkedList<int> ll, int k)
        {
            LinkedListNode<int> p1 = ll.First;
            LinkedListNode<int> p2 = ll.First;

Iterate through the loop till either p2 is null - which means linkedlist length is less than Kth element OR till the Kth element

            for (int i = 0; i < k; i++)
            {
                p2 = p2.Next;
                if (p2 == null)
                {
                    Console.WriteLine($"Linkedlist is smaller than {k}th Element");
                    return false;
                }
            }

Now, iterate both the pointers till p2 is null. Value containted in p1 pointer will correspond to Kth Element

            while (p2 != null)
            {
                p1 = p1.Next;
                p2 = p2.Next;
            }
            //p1 is the Kth Element
            Console.WriteLine($"Kth element is {p1.Value}");
            return true;
        }

I just handle the scenario with the help of the "size" variable which I have maintained during the operation(insert/delete).

   public int GetKthFromTheEnd(int node)
    {
        var sizeIndex = size; //  mantained the list size 
        var currentNode = first;
        while (sizeIndex-- >0)
        {
            if ((node - 1) == sizeIndex)
                return currentNode.value;

            currentNode = currentNode.next;
        }

        throw new ArgumentNullException();
    }