Given a linked list of size N. The task is to reverse every k nodes (where k is an input to the function) in the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should be considered as a group and must be reversed

24 0

Get full Expert solution in seconds

$1.97 ONLY

Unlock Answer

C++

Given a linked list of size N. The task is to reverse every k nodes (where k is an input to the function) in the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should be considered as a group and must be reversed

Example 1:

Input:
LinkedList: 1->2->2->4->5->6->7->8
K = 4
Output: 4 2 2 1 8 7 6 5 

Example 2:

Input:
LinkedList: 1->2->3->4->5
K = 3
Output: 3 2 1 5 4 

———————————————–

// { Driver Code Starts
#include<bits/stdc++.h>
using namespace std;


struct node
{
int data;
struct node* next;

node(int x){
data = x;
next = NULL;
}

};

/* Function to print linked list */
void printList(struct node *node)
{
while (node != NULL)
{
printf(“%d “, node->data);
node = node->next;
}
printf(“\n”);
}


// } Driver Code Ends

class Solution
{
public:
struct node *reverse (struct node *head, int k)
{
/////ENTER CODE HERE//////
}
};


// { Driver Code Starts.

/* Driver program to test above function*/
int main(void)
{
int t;
cin>>t;

while(t–)
{
struct node* head = NULL;
struct node* temp = NULL;
int n;
cin >> n;

for(int i=0 ; i<n ; i++)
{
int value;
cin >> value;
if(i == 0)
{
head = new node(value);
temp = head;
}
else
{
temp->next = new node(value);
temp = temp->next;
}
}

int k;
cin>>k;

Solution ob;
head = ob.reverse(head, k);
printList(head);
}

return(0);
}

// } Driver Code Ends

EXPERT ANSWER

#include<bits/stdc++.h>
using namespace std;


struct node
{
    int data;
    struct node* next;

    node(int x) {
        data = x;
        next = NULL;
    }

};

/* Function to print linked list */
void printList(struct node *node)
{
    while (node != NULL)
    {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\n");
}


// } Driver Code Ends


class Solution
{
public:
	//required method
    struct node *reverse (struct node *head, int k)
    {
    	//returning head if head is NULL
    	if(head==NULL){
    		return head;
		}
		//taking reference to current head
		node *backup=head;
		//and initializing a node reference to NULL
		node *curr=NULL;
		//looping for k times, or until head becomes NULL
		for(int i=0;i<k && head!=NULL;i++){
			//taking current head
			node *n=head;
			//advancing head reference
			head=head->next;
			//setting curr as next of old head
			n->next=curr;
			//setting n as new head
			curr=n;
		}
		//now making a recursive call, passing updated head, and k as arguments
		//setting the returned reference as next of previously backed up node.
		backup->next=reverse(head, k);
		//returning curr as new head
		return curr;
    }
};


int main(void)
{
    int t;
    cin>>t;

    while(t--)
    {
        struct node* head = NULL;
        struct node* temp = NULL;
        int n;
        cin >> n;

        for(int i=0 ; i<n ; i++)
        {
            int value;
            cin >> value;
            if(i == 0)
            {
                head = new node(value);
                temp = head;
            }
            else
            {
                temp->next = new node(value);
                temp = temp->next;
            }
        }

        int k;
        cin>>k;

        Solution ob;
        head = ob.reverse(head, k);
        printList(head);
    }

    return(0);
}


/*INPUT*/


2
8
1 2 2 4 5 6 7 8
4
5
1 2 3 4 5
3

/*OUTPUT*/


4 2 2 1 8 7 6 5
3 2 1 5 4