Infosys SP Technical Interview Questions

#include 
using namespace std;
class node
{
    public:
    int data;
    node* next;//defining linked list.

     
    node(int d)//making constructor for nodes
    {
        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<<"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<data<<" "; printList(head->next);
}
struct node* reverse(node* head, int k)//function to reverse linked list in groups
{
	if(head==NULL){
		return NULL;
	}
	struct node* next=NULL;
	struct node* prev=NULL;
	struct node* curr=head;
	int count=0;
	while(curr && count<k){ next=curr->next;
		curr->next=prev;
		prev=curr;
		curr=next;
		count++;
	}
	
	head->next=reverse(curr,k);
	return prev;
}
int main() //main function
{
    int k;
    node* head = NULL;
    
    int n = buildList(head);
    cout<<"Linked list data: ";
    printList(head);
    cout<<"\nEnter the group size: ";
    cin>>k;
    head=reverse(head,k);
    cout<<"\nAfter reversing linked list in groups of given size\n";
    cout<<"Linked list data: ";
    printList(head);//printing new linked list.
}

Output:
Enter the size of list:6

Enter data of the nodes
15
23
85
46
96
25
Linked list data: 15 23 85 46 96 25 
Enter the group size: 3

After reversing linked list in groups of given size
Linked list data: 85 23 15 25 96 46

#include   
#include  
struct Node         // Structure of node
{ 
	int item; 
	struct Node* next; 
}; 
struct Node *reverse (struct Node *head, int m) /* this function reverses the linked list in groups of size m and 
                                                    returns the pointer to the new head node*/
{ 
	struct Node* current = head; 
	struct Node* next = NULL; 
	struct Node* previous = NULL; 

void print_List(struct Node *node) //print function of the list
{
while (node != NULL)
{
printf("%d ",node->item);
node = node->next;
}
}
void insert(struct Node** head_ref, int new_data) //insert the data
{
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
new_Node->item = new_Data;
new_Node->next = (*head_ref);
(*head_ref) = new_Node;
}
int counter = 0;
while (current != NULL && counter < m) //reverse first m nodes of the linked list
{
next = current->next;
current->next = previous;
previous = current;
current = next;
counter++;
}

if (next != NULL)
head->next = reverse(next,m);
return previous;
}

int main()
{
struct Node* head = NULL;
insert(&head, 91);
insert(&head, 58);
insert(&head, 17);
insert(&head, 45);
insert(&head, 53);
insert(&head, 1);
insert(&head, 8);
insert(&head, 64);
insert(&head, 15);
insert(&head, 20);
printf("The linked list is: \n");
print_List(head);
head = reverse(head,4);
printf("\nReverse a Linked List in groups of given size like m = 4 here: \n");
print_List(head);
return(0);
}

Output:-
The linked list is: 
20  15  64  8  1  53  45  17  58  91
Reverse a Linked List in groups of given size like m = 4 here: 
8   64  15  20  17  45  53  1  91  58