Classic 150 Interview Questions P25 Reverse Nodes in k-Group

---

Timeline

Timeline

2025-11-20

init

linked list

---

Problem:

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 a node.

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, move forward k nodes.
			for (j = 0; j < k && p != nullptr; j++) {
				p = p->next;
			}

			if (p == nullptr) { // The last group has fewer 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) // Fewer 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;
        }
};