C++ program to append the last n nodes of a linked list to the beginning of the list

Append last n nodes of a linked list to the beginning of the list in C++

How to append the last n nodes of a linked list to its beginning?

In this article, we will learn how we can extract those n nodes and write a C++ program to append the last n nodes of a lined list to the beginning of the list. Appending last n nodes of a linked list to its beginning can be understood in a very simple way, it means to dig out or extract last n nodes of the linked list and append then to the beginning of the list.

Steps to write a C++ program to append the last n nodes of a linked list to the beginning of the list

S

T

E

P

S

To append last n nodes to the beginning of the list we need to follow the following steps

  1. Construct nodes and initialize the variables.
  2. Create methods to build list
  3. Now create a method to display or print the list.
  4. Now we will extract last n nodes from the list using append function.
  5. In the main function, first print last n nodes and then print remaining starting nodes.

In this way last n nodes will get append to beginning of the list.

S

T

E

P

S

To append last n nodes to the beginning of the list we need to follow the following steps

  1. Construct nodes and initialize the variables.
  2. Create methods to build list
  3. Now create a method to display or print the list.
  4. Now we will extract last n nodes from the list using append function.
  5. In the main function, first print last n nodes and then print remaining starting nodes.

In this way last n nodes will get append to beginning of the list.

How we can construct a linked list?

Syntax

class Node  

    int data; 
    Node *next; 
}; 

Using following set of codes in our program we can construct linked list.

C++ program to append last n nodes of a linked list to the beginning of the list

Algorithm to append last n nodes to the beginning of the list

A

L

G

O

R

I

T

H

M

To dig out last n nodes we need to follow following algorithm.

  1. WHILE (LAST!=NULL && I<N-K-1)
  2. LAST=LAST->NEXT
  3. I++
  4. END WHILE
  5. NODE *SECOND = LAST->NEXT
  6. LAST->NEXT=NULL
  7. RETURN SECOND

A

L

G

O

R

I

T

H

M

To dig out last n nodes we need to follow following algorithm.

  1. WHILE (LAST!=NULL && I<N-K-1)
  2. LAST=LAST->NEXT
  3. I++
  4. END WHILE
  5. NODE *SECOND = LAST->NEXT
  6. LAST->NEXT=NULL
  7. RETURN SECOND

Program to append the last n nodes of a linked list to its beginning in C++

#include <iostream>
using namespace std;
class node
{
    public:
    int data;
    node* next;

    //Constructor 
    node(int d)
    {
        data = d;
        next = NULL;
    }
};
void insertAtTail(node*&head,int data)//function to insert new element at tail of the list
{
    if(head == NULL){
        head = new node(data);
        return;
    }
    node *tail = head;
    while(tail->next != NULL){
        tail = tail->next;
    }
    tail->next = new node(data);
}
int buildList(node*&head)//function to build the list.
{
    int n;
    cout<<"Enter the size of list:";
    cin>>n;
    cout<<endl;
    int a=n;
    cout<<"<span style="color:#99cc00;">Enter data of the nodes\n";
    while(n--){
        int data;
        cin>>data;
        insertAtTail(head,data);//New element will be inserted at end.
    }
    return a;
}
void printList(node*head)//function to print linked list.
{
    if(head == NULL){
        return;
    }
    cout<<head->data<<" ";
    printList(head->next);
}
node* append(node*head,int k,int n)//function to find last n nodes
{
    node*last;
    last = head;
    int i=0;
    int ok = n-k-1; 
    while(last != NULL && i<ok)
    {
        last = last -> next;
       i++;
    }
    node*second = last->next;
    last->next = NULL;
    return second;
}
int main() //main function
{
    int k;
    node* head = NULL;
    int n = buildList(head);
    cout<<"Linked list data: ";
    printList(head);
    cout<<"\nEnter the value of 'n': ";
    cin>>k;
    node* temp = append(head,k,n);
    cout<<"\nAfter appending the last n nodes of a linked list to the beginning of the list\n";
    cout<<"Linked list data: ";
    printList(temp);// printing last n nodes
    printList(head);//printing remaining nodes
}
Output:
Enter the size of list:5

Enter data of the nodes
12
25
36
47
58
Linked list data: 12 25 36 47 58 
Enter the value of 'n': 3

After appending the last n nodes of a linked list to the beginning of the list
Linked list data: 36 47 58 12 25

Explore more about inserting element at end of singly linked list