컨베이어 상자 k묶음 뒤집기

문제

물류 창고의 컨베이어 위에 상자들이 한 줄로 놓여 있습니다. 상자들은 단일 연결 리스트로 관리되며, head가 맨 앞 상자입니다. 각 노드의 val은 상자의 관리 번호입니다.

포장 로봇은 컨베이어를 앞에서부터 k개씩 묶어 처리하는데, 한 묶음을 집어 올린 뒤 그 묶음 안의 순서를 뒤집어 다시 내려놓습니다. 앞에서부터 묶음을 만들다가 마지막에 남은 상자가 k개보다 적으면, 그 조각은 뒤집지 않고 원래 순서 그대로 둡니다.

head와 k가 주어질 때, 로봇이 모든 처리를 마친 뒤 컨베이어의 상태를 나타내는 연결 리스트의 head를 반환하는 solution(head, k) 함수를 작성하세요.

예시

예시 1 설명: [7,4,9]와 [2,5,8] 두 묶음이 각각 뒤집혀 [9,4,7], [8,5,2]가 됩니다.

예시 2 설명: [3,6], [1,8]은 뒤집히고, 마지막에 남은 [2]는 2개가 되지 않으므로 그대로 둡니다.

예시 3 설명: 상자가 k개보다 적어 묶음을 하나도 만들 수 없으므로 순서가 바뀌지 않습니다.

제약 조건

• 상자 개수 n: 0 ≤ n ≤ 100,000
• 1 ≤ k ≤ 100,000
• 0 ≤ Node.val ≤ 1,000,000
• 노드를 새로 만들지 않고 링크 연결만 바꿔 푸는 것을 권장합니다.

시간 복잡도 목표: O(n)