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