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;
{
return(NULL);
}
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)

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

1. private static void printnthFromtheLast(Node head, int i) {
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
System Required Functions:-
1- For Branches:-
b. Display Branch
c. Search for Branch by ID
2- For Account Holders:-