algo-aha

将组内第[2..k]元素依次插入到"上一组尾"prev之后。

子段反转

• https://leetcode.com/problems/reverse-linked-list-ii/

ListNode* reverseBetween(ListNode* head, int m, int n) {
	if (!head) return NULL;

	ListNode dummy(-1);
	dummy.next = head;
	auto prev = &dummy;
	for (int i = 1; i < m; i++) {
		prev = prev->next;
	}

	// 组头是反转后的组尾，将[m+1..n]的节点插入prev之后
	auto newtail = prev->next, curr = newtail->next;
	for (int i = m + 1; i <= n; i++) {
		newtail->next = curr->next;
		curr->next = prev->next;
		prev->next = curr;
		curr = newtail->next;
	}
	return dummy.next;
}

k个元素一组地反转

• https://leetcode.com/problems/reverse-nodes-in-k-group/

ListNode* reverseKGroup(ListNode* head, int k) {
	int len = 0;
	for (auto p = head; p; p = p->next) len++;

	ListNode dummy(-1);
	dummy.next = head;
	auto prev = &dummy;  // 组前的指针

	for (; len >= k; len -= k) {
		// 组头是反转后的组尾newtail，将组内第[2..k]元素插入到prev之后
		auto newtail = prev->next, curr = newtail->next;
		for (int i = 2; i <= k; i++) {
			newtail->next = curr->next;
			curr->next = prev->next;
			prev->next = curr;
			curr = newtail->next;
		}
		prev = newtail;
	}
	return dummy.next;
}