Problem Description:
Given a linked list, write a function to reverse every k nodes (where k is an input to the function).Ifalinked list is givenas1->2->3->4->5->6->7->8->NULL and k = 3 then output will be3->2->1->6->5->4->8->7->NULL.
Input:
In this problem,method takes two argument: the head of the linked list and int k. You should not read any input from stdin/console.
The struct Node has a data part which stores the data and a next pointer which points to the next element of the linked list.
There are multiple test cases. For each test case, this method will be called individually.
Output:
Reverse the linked list in the group of given size and return the reference of starting node(head) of the reversed Linked list .
Note:If you use “Test” or “Expected Output Button” use below example format
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
/* Reverse a linked list The input list will have at least one element Return the node which points to the head of the new LinkedList Node is defined as struct node { int data; struct Node *next; } */ struct node *reverse (struct node *head, int k) { // Complete this method node *tmp,*lastNode,*t; node *root; bool first=1; node *nNode,*nRoot; tmp=head; int total=0; int idx=0; while(tmp) { for(int i=1;i<=k;i++) { if(i==1) { nRoot=new node; nRoot->data=tmp->data; //nRoot->next=new node; lastNode=nRoot; } else { nNode=new node; nNode->data=tmp->data; nNode->next=nRoot; nRoot=nNode; } tmp=tmp->next; if(tmp==NULL) break; } if(first) { root=nRoot; first=0; } else { t=root; for(int i=2;i<=total;i++) { t=t->next; } t->next=nRoot; } total+=k; } return root; } |