Classic 150 Interview Questions P25 Reverse Nodes in k-Group

---

Timeline

timeline

2025-11-20

init

linked list

---

Title:

P25 K Reverse nodes in k-group

https://leetcode.cn/problems/reverse-nodes-in-k-group/description/?envType=study-plan-v2&envId=top-interview-150

In linked list problems, you generally cannot directly change the value of nodes.

Use head insertion to reverse the linked list. Create a dummy head node pointing to the first node of the first group. But when reaching the second group, use the tail node of the first group as the dummy head node. Otherwise, reversing the second group will break the connection between the last node of the first group and the first node of the second group.

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)
	{
		int i, j;
		ListNode *virt_head = new ListNode(0, head);
		ListNode *group_tail;
		ListNode *res = head;
		ListNode *tmp, *p;

		for (i = 0; virt_head->next != nullptr; i++) {
			p = virt_head;
			group_tail = virt_head->next; //The predecessor of the next group after reversal
			// Starting from virt_head, go forward k nodes
			for (j = 0; j < k && p != nullptr; j++) {
				p = p->next;
			}

			if (p == nullptr) { // The last group has less than k nodes
				break;
			}

			while (virt_head->next != p) {
				tmp = virt_head->next;
				virt_head->next = tmp->next;
				tmp->next = p->next;
				p->next = tmp;
			}
			if (i == 0) {
				res = virt_head->next;
				delete virt_head;
			}
			virt_head = group_tail;
		}

		return res;
	}
};

leetcode hot 100 rewrite：

class Solution {
    private:
        ListNode *reverse_list(ListNode *head_prev, ListNode *tail_next)
        {
                ListNode *head = head_prev->next;
                ListNode *prev = tail_next, *curr = head, *next;

                while (curr != tail_next) {
                        next = curr->next;
                        curr->next = prev;
                        prev = curr;
                        curr = next;
                }
                head_prev->next = prev;
                return head; // next prev
        }

    public:
        ListNode *reverseKGroup(ListNode *head, int k)
        {
                if (head == nullptr || k <= 1)
                        return head;

                int i;
                ListNode *virtual_head = new ListNode(0, head);
                ListNode *head_prev = virtual_head; // The node before the first node
                ListNode *tail_next = head; // The node after the last node

                while (tail_next != nullptr) {
                        for (i = 0; i < k; i++) {
                                if (tail_next != nullptr)
                                        tail_next = tail_next->next;
                                else
                                        break;
                        }
                        if (i != k) // less than k
                                break;

                        head_prev = reverse_list(head_prev, tail_next);
                        tail_next = head_prev->next;
                }

                head = virtual_head->next;
                delete virtual_head;
                return head;
        }
};