﻿ C Program: Reverse a singly linked list in blocks of size k

C Exercises: Reverse a singly linked list in blocks of size k

C Singly Linked List : Exercise-36 with Solution

Write a C program to reverse a singly linked list starting at the first position in blocks of size k.

Sample Solution:

C Code:

``````#include<stdio.h>
#include<stdlib.h>

// Structure defining a node in a singly linked list
struct Node {
int data;           // Data stored in the node
struct Node* next;  // Pointer to the next node
};

// Function to add a new node at the beginning of the linked list
void push_node(struct Node** head_ref, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));  // Allocate memory for a new node
new_node->data = new_data;  // Assign data to the new node
new_node->next = (*head_ref);  // Make the new node point to the current head
(*head_ref) = new_node;  // Move the head to point to the new node
}

// Function to reverse the first k nodes of a linked list
struct Node* reverse_k_nodes(struct Node* head, int k) {
struct Node* current = head;  // Pointer to the current node
struct Node* next = NULL;  // Pointer to store the next node
struct Node* prev = NULL;  // Pointer to store the previous node
int count = 0;  // Counter to track the number of nodes reversed

/* Reverse the first k nodes of the linked list */
while (current != NULL && count < k) {
next = current->next;  // Store the next node
current->next = prev;  // Reverse the link of current node to the previous node
prev = current;  // Move the prev pointer to the current node
current = next;  // Move the current pointer to the next node
count++;  // Increment the count of nodes reversed
}

/* Call recursively for the remaining nodes and link the two lists */
if (next != NULL) {
head->next = reverse_k_nodes(next, k);  // Recursively reverse the next set of k nodes
}

/* prev is now the head of the reversed sub-list */
return prev;
}

// Function to print the elements of a linked list
void printList(struct Node* node) {
while (node != NULL) {
printf("%d ", node->data);  // Print the data of the current node
node = node->next;  // Move to the next node
}
}

// Main function to demonstrate reversing the first k nodes of a linked list
int main() {

printList(head);  // Display the original list

head = reverse_k_nodes(head, 3);  // Reverse the first 3 nodes of the list
printf("\nReverse the first 3 nodes of the said Linked list: \n");
printList(head);  // Display the modified list

head = reverse_k_nodes(head, 5);  // Reverse the first 5 nodes of the list
printf("\nReverse the first 5 nodes of the said Linked list: \n");
printList(head);  // Display the modified list

return 0;
}
```
```

Sample Output:

```Given linked list:
1 2 3 4 5 6 7 8
Reverse the first 3 nodes of the said Linked list:
3 2 1 6 5 4 8 7
Reverse the first 5 nodes of the said Linked list:
5 6 1 2 3 7 8 4
```

Flowchart :

C Programming Code Editor:

What is the difficulty level of this exercise?

﻿