Reverse Alternate K nodes
You are given a Singly Linked List of integers and a positive integer 'K'. Modify the linked list by reversing every alternate 'K' nodes of the linked list.

A singly linked list is a type of linked list that is unidirectional, that is, it can be traversed in only one direction from head to the last node (tail).

Note:

If the number of nodes in the list or in the last group is less than 'K', just reverse the remaining nodes.

Example:

Linked list: 5 6 7 8 9 10 11 12 K: 3 Output: 7 6 5 8 9 10 12 11 We reverse the first 'K' (3) nodes and then skip the next 'K'(3) nodes. Now, since the number of nodes remaining in the list (2) is less than 'K', we just reverse the remaining nodes (11 and 12).

Note:

You need to reverse the first 'K' nodes and then skip the 'K' nodes and so on. 5 6 7 10 9 8 11 12 is not the correct answer for the given linked list.

Input Format

The first line of input contains an integer 'T', the number of test cases. The first line of every test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element. The second line of every test case contains the positive integer ‘K’.

Output Format:

For every test case, return the modified linked list. The elements of the modified list should be single-space separated, terminated by -1.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Reverse Alternate K nodes

You are given a Singly Linked List of integers and a positive integer 'K'. Modify the linked list by reversing every alternate 'K' nodes of the linked list.

A singly linked list is a type of linked list that is unidirectional, that is, it can be traversed in only one direction from head to the last node (tail).

Note:

If the number of nodes in the list or in the last group is less than 'K', just reverse the remaining nodes.

Example:

Linked list: 5 6 7 8 9 10 11 12
K: 3 

Output: 7 6 5 8 9 10 12 11

We reverse the first 'K' (3) nodes and then skip the next 'K'(3) nodes. Now, since the number of nodes remaining in the list (2) is less than 'K', we just reverse the remaining nodes (11 and 12).

Note:

You need to reverse the first 'K' nodes and then skip the 'K' nodes and so on. 5 6 7 10 9 8 11 12 is not the correct answer for the given linked list.

Input Format

The first line of input contains an integer 'T', the number of test cases.

The first line of every test case contains the elements of the singly linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.

The second line of every test case contains the positive integer ‘K’.

Output Format:

For every test case, return the modified linked list. The elements of the modified list should be single-space separated, terminated by -1.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 5 * 10^4
1 <= K <= N
-10^3 <= data <= 10^3 and data != -1

Time Limit: 1 sec

Accepted Answer

Recursively traverse the linked list. When returning from each recursive call keep track of the node number, considering the last node as number 1, second last as number 2 and so on. This counting could be tracked with the help of a global or pointer variable. With the help of this count variable, print the nodes having a node number less than or equal to k.

Accepted Answer

Recursion

The idea is very simple. We will process 2 * ‘K’ nodes at a time. Firstly, we will reverse the first ‘K’ nodes of the linked list and then we will skip the next ‘K’ nodes. We will do this recursively for the remaining linked list.

Algorithm:

If the node does not exist, simply return ‘NULL’.
Head is pointing to the first node of the linked list.
If there are less than ‘K’ nodes, just reverse them and return the reversed linked list. Else reverse the first ‘K’ nodes of the linked list.
After reversing the ‘K’ nodes, the head points to the ‘K’th node and the ‘K’th node in the original linked list will become the new head.
To connect the reversed part with the remaining part of the linked list, update the next of the head to (‘K’ + 1)th node.
As we don’t have to reverse the next ‘K’ nodes, we will skip them.
Now, recursively modify the rest of the linked list and link the two sub-linked lists.
Return the new head of the linked list.

Space Complexity: OtherExplanation:

O(N / (2 * K)), where ‘N’ is the number of nodes in the linked list and ‘K’ is the given positive integer.

In each recursive step, we are processing (2 * K) nodes of the linked list. Thus, O(N / (2 * K)) is the total recursion stack space used by the algorithm.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the linked list.

Since each node of the linked list is traversed exactly once, the final time complexity is O(N).

C++ (g++ 5.4)

/*
	Time Complexity: O(N)
	Space Complexity: O(N / (2 * K)) 
	
	where 'N' is the number of nodes in the linked list and 'K' is the given number. 
*/

Node* reverseAlternateKNodes(Node* head, int k)
{
	// Base condition.
	if(head == NULL)
	{
		return NULL;
	}
	
	Node* curr = head, *prev = NULL, *ahead = NULL;
	int count = k;
	
	// Reversing the first k nodes.
	while(curr != NULL and count > 0)
	{
		ahead = curr->next;
		curr->next = prev;
		prev = curr;
		curr = ahead; 
		count -= 1;
	}
	
	// Connecting the reversed linked list to the remaining list.
	head->next = curr; 
	count = k;
	
	// Skipping next k nodes. 
	while(curr != NULL and count > 1)
	{
		curr = curr->next;
		count -= 1;
	}
	
	// Recursively calling for the remaining list.
	if(curr != NULL)
	{
		curr->next = reverseAlternateKNodes(curr->next, k);
	}
	
	// Returning the new head.
	return prev;
}

Python (3.5)

'''

	Time Complexity: O(N)

	Space Complexity: O(N / (2 * K)) 

	

	Where N is the number of nodes in the linked list and K is the given number.	

'''



def reverseAlternateKNodes(head, k):



    # Base condition.

    if(head == None):

        return None



    curr, prev, ahead = head, None, None

    count = k



    # Reversing the first K nodes.

    while(curr != None and count > 0):

        ahead = curr.next

        curr.next = prev

        prev = curr

        curr = ahead

        count -= 1



    # Connecting the reversed linked list to the remaining list.

    head.next = curr

    count = k



    # Skipping next k nodes.

    while(curr != None and count > 1):

        curr = curr.next

        count -= 1



    # Recursively calling for the remaining list.

    if(curr != None):

        curr.next = reverseAlternateKNodes(curr.next, k)



    # Returning the new head.

    return prev

Java (SE 1.8)

/*
	Time Complexity: O(N)
	Space Complexity: O(N / (2 * K)) 
	
	where 'N' is the number of nodes in the linked list and 'K' is the given number. 
*/

import java.util.ArrayList;

public class Solution {
	public static Node reverseAlternateKNodes(Node head, int k) {
		// Base condition.
		if(head == null)
		{
			return null;
		}
		
		Node curr = head, prev = null, ahead = null;
		int count = k;
		
		// Reversing the first k nodes.
		while(curr != null && count > 0)
		{
			ahead = curr.next;
			curr.next = prev;
			prev = curr;
			curr = ahead; 
			count -= 1;
		}
		
		// Connecting the reversed linked list to the remaining list.
		head.next = curr; 
		count = k;
		
		// Skipping next k nodes. 
		while(curr != null && count > 1)
		{
			curr = curr.next;
			count -= 1;
		}
		
		// Recursively calling for the remaining list.
		if(curr != null)
		{
			curr.next = reverseAlternateKNodes(curr.next, k);
		}
		
		// Returning the new head.
		return prev;
	}
}

Accepted Answer

Iteratively

The idea is the same as used in the previous approach. This time, we will do it iteratively.

Head is pointing to the first node of the linked list.
Initialise a pointer to a Node ‘NEW_HEAD' that will point to the head of the final modified linked list.
Repeat the steps below until all the nodes are processed in the same way.

Reverse the first ‘K’ nodes of the linked list.
After reversing the ‘K’ nodes, the head points to the ‘K’th node.
If the 'NEW_HEAD' is ‘NULL’:
- If the Kth node in the original linked list exists, it will be the 'NEW_HEAD'.
- Else, the last node in the original linked list will be the 'NEW_HEAD'.
To connect the reversed part with the remaining part of the linked list, update the next of the head to (‘K’ + 1)th node.
As we don’t have to reverse the next ‘K’ nodes, we will skip them and move to the next iteration.

4. Return the new head of the linked list.

Note that we just have to set the new head once.

Space Complexity: O(1)Explanation:

O(1), as we are using constant extra memory.

We are just using a few pointers, which is constant in space. Thus, the final space complexity is O(1).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of nodes in the linked list.

Since each node of the linked list is traversed exactly once, the final time complexity is O(N).

Python (3.5)

'''

	Time Complexity: O(N)

	Space Complexity: O(1)



	Where N is the number of nodes in the linked list.

'''



def reverseAlternateKNodes(head, k):



    prev, curr, ahead = None, head, None

    tail, join = None, None

    newHead = None

    count = 0



    # Traverse the linked list to the end.

    while (curr != None):

        count = k

        join = curr

        prev = None



        # Reversing the k nodes.

        while (curr != None and count > 0):

            ahead = curr.next

            curr.next = prev

            prev = curr

            curr = ahead

            count -= 1



        # Update the new head for the modified linked list.

        if (newHead == None):

            newHead = prev



        #  Tail pointer is joined with the first node of the remaining linked list.

        if (tail != None):

            tail.next = prev



        tail = join

        tail.next = curr



        count = k



        # Skipping the next k nodes.

        while (curr != None and count > 0):

            prev = curr

            curr = curr.next

            count -= 1



        # Updating tail pointer for the next iteration.

        tail = prev



    # New head of the modified list is returned.

    return newHead

C++ (g++ 5.4)

/*
	Time Complexity: O(N)
	Space Complexity: O(1) 
	
	where 'N' is the number of nodes in the linked list.
*/

Node* reverseAlternateKNodes(Node* head, int k)
{	
	Node* prev = NULL, * curr = head, *ahead = NULL; 
    Node* tail = NULL, *join = NULL; 
    
    Node* newHead = NULL; 
    int count = 0; 
  
    // Traverse the linked list to the end.
    while (curr != NULL) 
	{ 
        count = k; 
        join = curr; 
        prev = NULL; 
  
        // Reversing the k nodes.
        while (curr != NULL && count > 0) 
		{ 
            ahead = curr->next; 
            curr->next = prev; 
            prev = curr; 
            curr = ahead; 
            count -= 1;
        } 
  
        // Update the new head for the modified linked list.
        if (newHead == NULL) 
        {
            newHead = prev; 
        }
  
        // Tail pointer is joined with the first node of the remaining linked list.
        if (tail != NULL)
        {
            tail->next = prev; 
        }
  
        tail = join; 
        tail->next = curr; 
  
        count = k; 
  
        // Skipping the next k nodes. 
        while (curr != NULL && count > 0) 
		{ 
            prev = curr; 
            curr = curr->next; 
            count -= 1;
        } 
  
        // Updating tail pointer for the next iteration. 
        tail = prev; 
    } 
  
    // New head of the modified list is returned. 
    return newHead;
	
	
}

Java (SE 1.8)

/*
	Time Complexity: O(N)
	Space Complexity: O(1) 
	
	where 'N' is the number of nodes in the linked list.
*/

import java.util.ArrayList;

public class Solution {
	public static Node reverseAlternateKNodes(Node head, int k) {
		Node prev = null,  curr = head, ahead = null; 
	    Node tail = null, join = null; 
	    
	    Node newHead = null; 
	    int count = 0; 
	  
	    // Traverse the linked list to the end.
	    while (curr != null) 
		{ 
	        count = k; 
	        join = curr; 
	        prev = null; 
	  
	        // Reversing the k nodes.
	        while (curr != null && count > 0) 
			{ 
	            ahead = curr.next; 
	            curr.next = prev; 
	            prev = curr; 
	            curr = ahead; 
	            count -= 1;
	        } 
	  
	        // Update the new head for the modified linked list.
	        if (newHead == null) 
	        {
	            newHead = prev; 
	        }
	  
	        // Tail pointer is joined with the first node of the remaining linked list.
	        if (tail != null)
	        {
	            tail.next = prev; 
	        }
	  
	        tail = join; 
	        tail.next = curr; 
	  
	        count = k; 
	  
	        // Skipping the next k nodes. 
	        while (curr != null && count > 0) 
			{ 
	            prev = curr; 
	            curr = curr.next; 
	            count -= 1;
	        } 
	  
	        // Updating tail pointer for the next iteration. 
	        tail = prev; 
	    } 
	  
	    // New head of the modified list is returned. 
	    return newHead;
	}
}

You are given a Singly Linked List of integers and a positive integer 'K'. Modify the linked list by reversing every alternate 'K' nodes of the linked list.

Note:

Example:

Note:

Input Format

Output Format:

Note:

Constraints:

Top Nagarro Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Nagarro Software Developer