Reverse Nodes In K Group

                                            
/**
 * 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) {
        ListNode* curr = head;
        int count = 0;
        while (curr != nullptr && count < k) {
            curr = curr->next;
            count++;
        }
        if (count == k) {
            ListNode* reversedHead = reverseLinkedList(head, k);
            head->next = reverseKGroup(curr, k);
            return reversedHead;
        }
        return head;
    }

    ListNode* reverseLinkedList(ListNode* head, int k) {
        ListNode *prev = nullptr, *curr = head, *next = nullptr;
        while (k > 0 && curr != nullptr) {
            next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
            k--;
        }
        return prev;
    }
};

                                            
/**
 * 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 || k == 1) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode start = dummy;
        ListNode end = head;
        int count = 0;
        
        while (end != null) {
            count++;
            if (count % k == 0) {
                start = reverse(start, end.next);
                end = start.next;
            } else {
                end = end.next;
            }
        }
        
        return dummy.next;
    }
    
    private ListNode reverse(ListNode start, ListNode end) {
        ListNode prev = start;
        ListNode curr = start.next;
        ListNode first = curr;
        
        while (curr != end) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        
        start.next = prev;
        first.next = curr;
        return first;
    }
}

                                            
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseKGroup(self, head, k):
        def reverseLinkedList(head, k):
            prev = None
            curr = head
            while k > 0:
                next_node = curr.next
                curr.next = prev
                prev = curr
                curr = next_node
                k -= 1
            return prev

        def getLength(head):
            length = 0
            while head:
                length += 1
                head = head.next
            return length

        length = getLength(head)
        dummy = ListNode(0)
        dummy.next = head
        prev_group_end = dummy
        while length >= k:
            group_start = prev_group_end.next
            group_end = group_start
            for _ in range(k - 1):
                group_end = group_end.next
            next_group_start = group_end.next
            group_end.next = None
            prev_group_end.next = reverseLinkedList(group_start, k)
            group_start.next = next_group_start
            prev_group_end = group_start
            length -= k
        return dummy.next

                                            
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* reverseKGroup(struct ListNode* head, int k) {
    if (!head || k == 1) {
        return head;
    }
    
    struct ListNode* dummy = malloc(sizeof(struct ListNode));
    dummy->next = head;
    struct ListNode *cur = dummy, *nex = dummy, *pre = dummy;
    int count = 0;
    
    while (cur->next) {
        cur = cur->next;
        count++;
    }
    
    while (count >= k) {
        cur = pre->next;
        nex = cur->next;
        for (int i = 1; i < k; i++) {
            cur->next = nex->next;
            nex->next = pre->next;
            pre->next = nex;
            nex = cur->next;
        }
        pre = cur;
        count -= k;
    }
    
    return dummy->next;
}

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

                                            
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
    const reverse = (start: ListNode, end: ListNode) => {
        let prev = null;
        let curr = start;
        while (curr !== end) {
            const nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    };
    
    let count = 0;
    let current = head;
    while (count < k && current) {
        current = current.next;
        count++;
    }
    
    if (count < k) {
        return head;
    }
    
    const newHead = reverse(head, current);
    head.next = reverseKGroup(current, k);
    
    return newHead;
}

                                            
/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {
    /**
     * @param ListNode $head
     * @param Integer $k
     * @return ListNode
     */
    function reverseKGroup($head, $k) {
        $count = 0;
        $current = $head;
        while ($count < $k && $current != null) {
            $current = $current->next;
            $count++;
        }
        
        if ($count == $k) {
            $reversedHead = $this->reverseList($head, $k);
            $head->next = $this->reverseKGroup($current, $k);
            return $reversedHead;
        }
        
        return $head;
    }
    
    function reverseList($head, $k) {
        $prev = null;
        $current = $head;
        $next = null;
        
        while ($k > 0 && $current != null) {
            $next = $current->next;
            $current->next = $prev;
            $prev = $current;
            $current = $next;
            $k--;
        }
        
        return $prev;
    }
}

                                            
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func reverseKGroup(_ head: ListNode?, _ k: Int) -> ListNode? {
        var count = 0
        var current = head
        
        while current != nil, count < k {
            current = current?.next
            count += 1
        }
        
        if count == k {
            var prev: ListNode? = nil
            var next: ListNode? = nil
            var current = head
            
            for _ in 0..<k {
                next = current?.next
                current?.next = prev
                prev = current
                current = next
            }
            
            if let next = next {
                head?.next = reverseKGroup(next, k)
            }
            
            return prev
        }
        
        return head
    }
}

                                            
/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun reverseKGroup(head: ListNode?, k: Int): ListNode? {
        fun reverseLinkedList(head: ListNode?, k: Int): ListNode? {
            var count = 0
            var temp = head
            while (count < k) {
                if (temp == null) {
                    return head
                }
                temp = temp.next
                count++
            }
            
            var prev: ListNode? = null
            var current = head
            var next: ListNode?
            count = 0
            while (count < k) {
                next = current?.next
                current?.next = prev
                prev = current
                current = next
                count++
            }
            
            head?.next = reverseLinkedList(current, k)
            return prev
        }
        
        return reverseLinkedList(head, k)
    }
}

                                            
/**
 * Definition for singly-linked list.
 * class ListNode(_x: Int = 0, _next: ListNode = null) {
 *   var next: ListNode = _next
 *   var x: Int = _x
 * }
 */
object Solution {
    def reverseKGroup(head: ListNode, k: Int): ListNode = {
        def reverse(head: ListNode, tail: ListNode): ListNode = {
            var prev: ListNode = null
            var curr = head
            while (curr != tail) {
                val nextTemp = curr.next
                curr.next = prev
                prev = curr
                curr = nextTemp
            }
            prev
        }

        var count = 0
        var curr = head
        while (count < k && curr != null) {
            curr = curr.next
            count += 1
        }

        if (count == k) {
            val reversedHead = reverse(head, curr)
            head.next = reverseKGroup(curr, k)
            reversedHead
        } else {
            head
        }
    }
}

Explanation

To solve this coding challenge, we need to reverse the nodes of a linked list in groups of given size

k

without altering their values, just reordering the nodes themselves. Here's a detailed breakdown of how this can be achieved:

Understanding the problem : Given a linked list, we need to reverse every
k

nodes. If
k

does not perfectly divide the length of the list, the remaining nodes at the end are left as they are.
Constraints :

Reversing the nodes in groups of
k

.
If the number of nodes is not a multiple of
k

, remainder nodes will stay the same.
The solution should ideally use O(1) extra memory, meaning in-place modifications are preferred.

Approach :

Firstly, write a helper function to reverse a sublist of
k

nodes within the linked list.
Secondly, traverse the whole linked list to determine the total number of nodes.
Use a dummy node to handle edge cases easily.
Reverse the nodes in groups of
k

and link them properly.

Here is the breakdown of our approach in pseudocode:

Detailed Steps in Pseudocode

Define reverseLinkedList function : This function will reverse a portion of the linked list.

                                            
FUNCTION reverseLinkedList(head, k):
prev = NULL
curr = head
WHILE k > 0:
next_node = curr.next  # Store the next node
curr.next = prev       # Reverse the current node's pointer
prev = curr            # Move prev to current node
curr = next_node       # Move to next node
k -= 1
RETURN prev  # Return the new head of the reversed list

Define getLength function : This function will calculate the length of the linked list.

                                            
FUNCTION getLength(head):
length = 0
WHILE head != NULL:
length += 1
head = head.next
RETURN length

Main function to reverse nodes in groups of k :

                                            
FUNCTION reverseKGroup(head, k):
length = getLength(head)  # Determine the length of the list

dummy = new ListNode(0)  # Create a dummy node
dummy.next = head
prev_group_end = dummy

WHILE length >= k:
group_start = prev_group_end.next  # Starting node of the group
group_end = group_start

FOR i = 1 TO k-1:  # Find the end of this k-group
group_end = group_end.next

next_group_start = group_end.next  # Node to start the next group
group_end.next = NULL  # Temporarily break the link to the next group

prev_group_end.next = reverseLinkedList(group_start, k)  # Reverse this k-group and connect it

group_start.next = next_group_start  # Connect the previous group's start to the next group

prev_group_end = group_start  # Move the prev_group_end to the end of the reversed group
length -= k  # Reduce the length by k as we've processed this group

RETURN dummy.next  # Return the head of the new modified list

By following these steps, we ensure that we correctly reverse the nodes in groups of

k

while maintaining the remainder nodes as they are if

k

does not divide the length of the list completely. The use of a dummy node simplifies edge cases like when the list has fewer nodes initially or when it gets completely reversed. This solution also aims to use O(1) extra memory by manipulating pointers directly without using additional data structures.