# Append Last N Nodes to First in the Linked List using C++ program

Here, we are going to learn **how to append last N nodes to first in the linked list using a C++ program**?

Submitted by Indrajeet Das, on December 19, 2018

Given a linked list and an integer n, append the last n elements of the LL to front. Assume given n will be smaller than length of LL.

**Input format:** Line 1: Linked list elements (separated by space and terminated by -1

Sample Input 1 : 1 2 3 4 5 -1 3 Sample Output 1 : 3 4 5 1 2

**Description:**

The question asks us to append the last N nodes to front, i.e the new linked list should first start from those N nodes and then traverse the rest of the nodes through the head of the old linked list.

**Example:**

For Linked List 1->2->3->4->5->6->NULL To append the last 2 nodes, the new linked list should be: 5->6->1->2->3->4->NULL

**Solution Explanation:**

To solve this problem, we take two pointers temp and t and point both of them to the head of the linked list. We take another variable i and equate it to – n. This i is used for finding out the head of the new linked list. Then we traverse the loop while temp != NULL. In the loop we check that if(i>=0) i.e temp is now n nodes away from t, t = t-> next. We will update i++ and temp = temp->next on each traversal. At last, we update temp-> next = head, head = t -> next and t-> next = NULL.

**Algorithm:**

- STEP 1: Declare the function appendNNode with parameters (Node* head, int n)
- STEP 2: Declare two variables Node * temp , t and point both of them to head.
- STEP 3: Declare int i = -n
- STEP 4: Repeat Step 5 and 6, while(temp->next != NULL)
- STEP 5: if(i>=0) t = t-> next.
- STEP 6: temp = temp-> next, i++.
- STEP 7: temp->next = head, head = t->next, and t-> next =NULL
- STEP 8: return head

**Steps:**

At first: 1->2->3->4->5->6->NULL, t->1 and temp->1. After complete traversal: 1->2->3->4->5->6->NULL, t->4 and temp->6. So, temp->next = head and head = t->next i.e 5->6->1->2->3->4 --- (reconnecting to 5) Atlast, t-> next = NULL i.e 5->6->1->2->3->4->NULL

**Function:**

Node *appendNNodes(Node* head, int n){ // Two pointers, one for traversal and // other for finding the new head of LL Node *temp = head, *t = head; //index maintained for finding new head int i = -n; while(temp->next!=NULL){ //When temp went forward n nodes from t if(i>=0){ t = t->next; } temp = temp ->next; i++; } //Connecting the tail to head temp->next = head; //Assigning the new node head = t->next; //Deleting the previous connection t->next = NULL; return head; }

**C++ Code:**

#include<bits/stdc++.h> using namespace std; struct Node{// linked list Node int data; Node * next; }; Node *newNode(int k){ //defining new node Node *temp = (Node*)malloc(sizeof(Node)); temp->data = k; temp->next = NULL; return temp; } //Used to add new node at the end of the list Node *addNode(Node* head, int k){ if(head == NULL){ head = newNode(k); } else{ Node * temp = head; Node * node = newNode(k); while(temp->next!= NULL){ temp = temp->next; } temp-> next = node; } return head; } // Used to create new linked list and return head Node *createNewLL(){ int cont = 1; int data; Node* head = NULL; while(cont){ cout<<"Enter the data of the Node"<<endl; cin>>data; head = addNode(head,data); cout<<"Do you want to continue?(0/1)"<<endl; cin>>cont; } return head; } //To print the Linked List void *printLL(Node * head){ while(head!= NULL){ cout<<head->data<<"->"; head = head-> next; } cout<<"NULL"<<endl; } //Function Node *appendNNodes(Node* head, int n){ // Two pointers, one for traversal and // other for finding the new head of LL Node *temp = head, *t = head; //index maintained for finding new head int i = -n; while(temp->next!=NULL){ //When temp went forward n nodes from t if(i>=0){ t = t->next; } temp = temp ->next; i++; } //Connecting the tail to head temp->next = head; //Assigning the new node head = t->next; //Deleting the previous connection t->next = NULL; return head; } //Driver Main int main(){ Node * head = createNewLL(); cout<<"The linked list is"<<endl; printLL(head); int data; cout<<"Enter the number of nodes you want to append."<<endl; cin>>data; head = appendNNodes(head,data); cout<<"The new Linked List is" <<endl; printLL(head); return 0; }

**Output**

Enter the data of the Node 1 Do you want to continue?(0/1) 1 Enter the data of the Node 2 Do you want to continue?(0/1) 1 Enter the data of the Node 3 Do you want to continue?(0/1) 1 Enter the data of the Node 4 Do you want to continue?(0/1) 1 Enter the data of the Node 5 Do you want to continue?(0/1) 1 Enter the data of the Node 6 Do you want to continue?(0/1) 1 Enter the data of the Node 7 Do you want to continue?(0/1) 0 The linked list is 1->2->3->4->5->6->7->NULL Enter the number of nodes you want to append. 3 The new Linked List is 5->6->7->1->2->3->4->NULL

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.