Write a C program to return the nth node from the end of a linked list

Solution 01 -
Brute Force Approach:
Let’s assume length of linked list be ‘L’ ,
nth node from end = L – n + 1 node from start.
Step 1: Iterate over the linked list and determine its length.
Step 2: Now using the above mentioned formula , we can determine the position of the required node.
Step 3: So we iterate the linked list again  till we reach the required node.
Step 4: Return the required node.
Solution 02 -

Suppose one needs to get to the 6th node from the end in this LL. First, just keep on incrementing the first pointer (ptr1) till the number of increments cross n (which is 6 in this case)

Step 1 : 1(ptr1,ptr2) -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10

Step 2 : 1(ptr2) -> 2 -> 3 -> 4 -> 5 -> 6(ptr1) -> 7 -> 8 -> 9 -> 10

Now, start the second pointer (ptr2) and keep on incrementing it till the first pointer (ptr1) reaches the end of the LL.

Step 3 : 1 -> 2 -> 3 -> 4(ptr2) -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 (ptr1)

So here you have!, the 6th node from the end pointed to by ptr2!

Here is some C code.

struct node
{
	int data;
	struct node *next;
}mynode;




mynode * nthNode(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->next) != NULL)
		{
			ptr1 =ptr1->next;
		}
		else
			return NULL;
	}
	while((ptr1->next) != NULL)
	{
		ptr1 = ptr1->next;
		ptr2=ptr2->next;
	}
	return(ptr2);
}

Complexity:

  • Time Complexity: O(n)
  • Space Complexity: O(1)

2 Thoughts on “Write a C program to return the nth node from the end of a linked list

  1. Ajay on June 8, 2015 at 12:00 am said:

    private static void printnthFromtheLast(Node head, int i) {
    Node ptr1 = head;
    Node ptr2=head;
    int count =0;
    while(count<i)
    {
    if(ptr2==null)
    {

    break;
    }
    ptr2=ptr2.getNext();
    count++;
    }
    if(ptr2==null || i<0)
    {
    System.out.println("Invalid Data");
    return;
    }
    while(ptr1!=null && ptr2!=null)
    {
    ptr2=ptr2.getNext();
    ptr1=ptr1.getNext();
    }
    System.out.println(ptr1.getData());
    }

  2. moataz elkady on December 7, 2015 at 10:10 pm said:

    This project manages the bank activities. The bank has many branches. Each branch
    has basic information (Name, ID, Manager). The bank deals with many account
    holders and each holder may have many accounts. Each holder has basic information
    (Name, ID, Address, Balance).
    System Required Functions:-
    1- For Branches:-
    a. Add new branch
    b. Display Branch
    c. Search for Branch by ID
    2- For Account Holders:-
    a. Add new holder
    b. Remove a holder
    c. Display holder data
    d. Search for holder by Name
    Bonus:-
     Update Holder Information
     Remove Branch
     Display holders of a branch ordered by their balances
     Given a Branch id, display Holders in that Branch

Leave a Reply to Ajay Cancel reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation