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 MCQs

Comments and Discussions!