Register for our webinar

### How to Nail your next Technical Interview

1 hour
1
Enter details
2
Select webinar slot
*Invalid Name
*Invalid Name
Step 1
Step 2
Congratulations!
You have registered for our webinar
Oops! Something went wrong while submitting the form.
1
Enter details
2
Select webinar slot
*All webinar slots are in the Asia/Kolkata timezone
Step 1
Step 2
Confirmed
You are scheduled with Interview Kickstart.
Redirecting...
Oops! Something went wrong while submitting the form.

## You may be missing out on a 66.5% salary hike*

### Nick Camilleri

Head of Career Skills Development & Coaching
*Based on past data of successful IK students
Help us know you better!

## How many years of coding experience do you have?

Oops! Something went wrong while submitting the form.

## FREE course on 'Sorting Algorithms' by Omkar Deshpande (Stanford PhD, Head of Curriculum, IK)

Oops! Something went wrong while submitting the form.

# Reverse A Linked List In Groups Of K Problem Statement

Given a linked list, reverse every group of `k` nodes. If there is a remainder (a group of less than `k` nodes) in the end, reverse that last group, too.

## Example One

``````{
"head": [1, 2, 3, 4, 5, 6],
"k": 3
}
``````

Output:

``````[3, 2, 1, 6, 5, 4]
``````

Input list consists of two whole groups of three. In the output list the first three and last three nodes are reversed.

## Example Two

``````{
"head": [1, 2, 3, 4, 5, 6, 7, 8],
"k": 3
}
``````

Output:

``````[3, 2, 1, 6, 5, 4, 8, 7]
``````

There are two whole groups of three and one partial group (a remainder that consists of just two nodes). Each of the three groups is reversed in the output.

## Notes

• The function has two parameters: head of the given linked list and `k`.
• Return the head of the linked list after reversing the groups of nodes in it.

Constraints:

• 1 <= number of nodes in the list <= 100000
• -2 * 109 <= node value <= 2 * 109
• 1 <= `k` <= number of nodes
• Cannot use more than constant extra space

We have provided one solution for this problem.

# Reverse A Linked List In Groups Of K Solution: Iterative

The "constant extra space" constraint rules out using recursion because recursion uses the call stack space (up to O(n) if `k = n`).

We are forced to use an iterative approach.

This solution demonstrates how that can be implemented.

O(n).

O(1).

O(n).

## Code For Reverse A Linked List In Groups Of K Solution: Iterative

``````/*
Asymptotic complexity in terms of length of given linked list \`n\`:
* Time: O(n).
* Auxiliary space: O(1).
* Total space: O(n).
*/

// Helper function: Reverse singly linked list in O(length) time and O(1) extra space.
{
while (cur)
{
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
}

{
/*
Input:
list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL
k: 3
Output:
3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 8 -> 7-> NULL
Groups to be reversed are (1 -> 2 -> 3), (4 -> 5 -> 6) and (7 -> 8).

We will call reverse_linked_list function when (start = 1 and stop = 3),
(start = 4 and stop = 6) and (start = 7 and stop = 8).
*/
// Points to previous start node.
int count = 0;
while (stop)
{
count++;
/*
If we have covered k nodes in between start
and stop (inclusive) or we are at the last node.
*/
if (count == k || stop->next == NULL)
{
// Points to next node of start.
/*
We want to reverse start to stop nodes,
set stop->next = NULL so we know where to stop.
*/
stop->next = NULL;
// Reverse start to stop nodes.
if (prev_of_start == NULL)
{
// Head will change when we are reversing the linked list first time.
}
else
{
/*
We have reversed start to stop nodes, hence now stop will be next node of
prev_of_start.
*/
prev_of_start->next = stop;
}
/*
We have reversed start to stop nodes, hence next_of_stop will be next node of start.
*/
start->next = next_of_stop;
/*
In the above example, after we have reversed first k nodes list will be:
3 -> 2 -> 1 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL,
start will point to 1, next_of_stop will point to 4.

Now we will set start and stop to point at 4.
And prev_of_start should be previous of 4 that is 1.
*/
prev_of_start = start;
start = next_of_stop;
stop = next_of_stop;
// Reset counter.
count = 0;
}
else
{
stop = stop->next;
}
}
}

``````

We hope that these solutions to reverse a linked list in groups of k problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

### Try yourself in the Editor

Note: Input and Output will already be taken care of.

# Reverse A Linked List In Groups Of K Problem Statement

Given a linked list, reverse every group of `k` nodes. If there is a remainder (a group of less than `k` nodes) in the end, reverse that last group, too.

## Example One

``````{
"head": [1, 2, 3, 4, 5, 6],
"k": 3
}
``````

Output:

``````[3, 2, 1, 6, 5, 4]
``````

Input list consists of two whole groups of three. In the output list the first three and last three nodes are reversed.

## Example Two

``````{
"head": [1, 2, 3, 4, 5, 6, 7, 8],
"k": 3
}
``````

Output:

``````[3, 2, 1, 6, 5, 4, 8, 7]
``````

There are two whole groups of three and one partial group (a remainder that consists of just two nodes). Each of the three groups is reversed in the output.

## Notes

• The function has two parameters: head of the given linked list and `k`.
• Return the head of the linked list after reversing the groups of nodes in it.

Constraints:

• 1 <= number of nodes in the list <= 100000
• -2 * 109 <= node value <= 2 * 109
• 1 <= `k` <= number of nodes
• Cannot use more than constant extra space

We have provided one solution for this problem.

# Reverse A Linked List In Groups Of K Solution: Iterative

The "constant extra space" constraint rules out using recursion because recursion uses the call stack space (up to O(n) if `k = n`).

We are forced to use an iterative approach.

This solution demonstrates how that can be implemented.

O(n).

O(1).

O(n).

## Code For Reverse A Linked List In Groups Of K Solution: Iterative

``````/*
Asymptotic complexity in terms of length of given linked list \`n\`:
* Time: O(n).
* Auxiliary space: O(1).
* Total space: O(n).
*/

// Helper function: Reverse singly linked list in O(length) time and O(1) extra space.
{
while (cur)
{
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
}

{
/*
Input:
list: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL
k: 3
Output:
3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 8 -> 7-> NULL
Groups to be reversed are (1 -> 2 -> 3), (4 -> 5 -> 6) and (7 -> 8).

We will call reverse_linked_list function when (start = 1 and stop = 3),
(start = 4 and stop = 6) and (start = 7 and stop = 8).
*/
// Points to previous start node.
int count = 0;
while (stop)
{
count++;
/*
If we have covered k nodes in between start
and stop (inclusive) or we are at the last node.
*/
if (count == k || stop->next == NULL)
{
// Points to next node of start.
/*
We want to reverse start to stop nodes,
set stop->next = NULL so we know where to stop.
*/
stop->next = NULL;
// Reverse start to stop nodes.
if (prev_of_start == NULL)
{
// Head will change when we are reversing the linked list first time.
}
else
{
/*
We have reversed start to stop nodes, hence now stop will be next node of
prev_of_start.
*/
prev_of_start->next = stop;
}
/*
We have reversed start to stop nodes, hence next_of_stop will be next node of start.
*/
start->next = next_of_stop;
/*
In the above example, after we have reversed first k nodes list will be:
3 -> 2 -> 1 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL,
start will point to 1, next_of_stop will point to 4.

Now we will set start and stop to point at 4.
And prev_of_start should be previous of 4 that is 1.
*/
prev_of_start = start;
start = next_of_stop;
stop = next_of_stop;
// Reset counter.
count = 0;
}
else
{
stop = stop->next;
}
}
}

``````

We hope that these solutions to reverse a linked list in groups of k problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as: