Solution For Reverse Nodes In K Group

The problem “Reverse Nodes in K-Group” asks us to reverse each group of k nodes in a linked list such that the nodes in a group are linked in reverse order. If the number of nodes in the last group is less than k, we should leave those nodes as they are.

We can solve this problem by following a recursive approach. We’ll use a recursive function that takes the head of a linked list and the value of k as input. The function will reverse the first group of k nodes and call itself recursively for the remaining part of the list. The base condition for the function will be when the list has less than k nodes, in which case we’ll just return the head of the list.

Here’s how we can implement this approach:

1. Define the recursive function reverseKGroup(head, k), where head is the head of the linked list and k is the group size.
2. Create a variable called count and initialize it to 0. Also create a variable called current and initialize it to head.
3. Traverse the list using a while loop until the end of the list or until count == k.
4. Inside the loop, increment count and move current to the next node.
5. Check if count == k. If it is, we’ll reverse the current group of k nodes.
6. To reverse the current group, we’ll define a new variable called prev and initialize it to None. Also create a variable called next and initialize it to None.
7. While count > 0, do the following:
8. Set next to current.next.
9. Set current.next to prev.
10. Set prev to current.
11. Set current to next.
12. Decrement count.
13. After reversing the group, set head.next to reverseKGroup(current, k).
14. Return prev as the new head of the reversed group.

Here’s the Python implementation of the recursive approach:

def reverseKGroup(head, k):
count = 0
current = head
while current and count < k:
current = current.next
count += 1
if count == k:
# Reverse the current group
prev, next = None, None
current = head
while count > 0:
next = current.next
current.next = prev
prev = current
current = next
count -= 1
# Recursively call for rest of the list
head.next = reverseKGroup(current, k)
# Return the new head of the reversed group
return prev
else:
# Base case, list has less than k nodes
return head

That’s it! We’ve successfully solved the “Reverse Nodes in K-Group” problem using a recursive approach.

Step by Step Implementation For Reverse Nodes In K Group

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;
        
        while (curr != null) {
            int i = 0;
            while (curr != null && i < k) {
                curr = curr.next;
                i++;
            }
            
            if (i == k) {
                ListNode next = curr;
                curr = prev.next;
                i = 0;
                
                while (i < k) {
                    next = curr.next;
                    curr.next = prev.next;
                    prev.next = curr;
                    curr = next;
                    i++;
                }
                
                prev = curr;
                curr = next;
            }
        }
        
        return dummy.next;
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        # reverse nodes in k groups and return the head of the new list
        # edge case: if k is 1 or 0, then the list does not need to be reversed
        if k <= 1:
            return head
        
        # create a dummy node to use as the head of the new list
        dummy = ListNode()
        dummy.next = head
        prev = dummy
        
        # reverse the nodes in each group of k
        while head:
            # reverse the next k nodes
            prev, end = self.reverse(prev, head, k)
            # set head to the node after the end of the current group
            head = end.next
            
        return dummy.next
    
    def reverse(self, prev, head, k):
        # reverse the next k nodes starting at head
        # return the new head and end of the reversed group
        
        # edge case: if there are fewer than k nodes remaining, do not reverse them
        if not head or not head.next:
            return (prev, head)
        
        # set the end node to be the kth node
        end = head
        for i in range(k-1):
            # if there are fewer than k nodes remaining, do not reverse them
            if not end or not end.next:
                return (prev, end)
            end = end.next
        
        # reverse the next k nodes
        curr = head
        next = curr.next
        while curr != end:
            temp = next.next
            next.next = curr
            curr.next = end.next
            prev.next = next
            next = temp
            curr = prev.next
        
        return (prev, curr)

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

Only constant extra memory is allowed.
You may not alter the values in the list's nodes, only nodes itself may be changed.

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var reverseKGroup = function(head, k) {
    // reverse first k nodes
    let current = head;
    let next = null;
    let prev = null;
    let count = 0;
    
    while (current !== null && count < k) {
        next = current.next;
        current.next = prev;
        prev = current;
        current = next;
        count++;
    }
    
    // next is now a pointer to (k+1)th node
    // recursively call for the list starting from current
    // and make rest of the list as next of first node
    if (next !== null) {
        head.next = reverseKGroup(next, k);
    }
    
    // prev is now head of input list
    return prev;
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head==NULL || k==1) return head;
        int num=0;
        ListNode *preheader = new ListNode(-1);
        preheader->next = head;
        ListNode *cur = preheader, *nex, *pre = preheader;
        while(cur = cur->next) 
            num++;
        while(num>=k) {
            cur = pre->next;
            nex = cur->next;
            for(int i=1;inext=nex->next;
                nex->next=pre->next;
                pre->next=nex;
                nex=cur->next;    
            }
            pre = cur;
            num-=k;
        }
        return preheader->next;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode ReverseKGroup(ListNode head, int k) {
        //edge case
        if(head == null || k <= 1){
            return head;
        }
        
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy, curr = head;
        
        //reverse k nodes for each iteration
        while(curr != null){
            int count = 1;
            //check if there are k nodes left to reverse
            while(curr.next != null && count < k){
                curr = curr.next;
                count++;
            }
            //if there are not k nodes left, return the current head
            if(count < k){
                return dummy.next;
            }
            //store the next node to reverse
            ListNode next = curr.next;
            //reverse the current k nodes
            curr.next = null;
            ReverseList(prev, next);
            //move the pointers
            prev = head;
            curr = next;
            head = next;
        }
        return dummy.next;
    }
    
    //helper function to reverse a singly linked list
    private ListNode ReverseList(ListNode prev, ListNode next){
        //edge case
        if(prev == null || prev.next == null){
            return prev;
        }
        ListNode curr = prev.next;
        ListNode last = prev.next;
        while(curr != null){
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        //set the end of the reversed list to point to the next node to reverse
        last.next = next;
        //set the head of the reversed list to the previous node
        return prev;
    }
}