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?
By Indrajeet Das Last updated : August 01, 2023

Problem statement

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.

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

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

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

Appending Last N Nodes to First in the Linked List

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

Algorithm

The steps to append last n nodes to first in the linked list are:

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

Consider these steps with an example -

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 / Pseudo Code

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++ program to append the last n nodes of a linked list to the beginning of the list

#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