What is the best way to solve Reverse Nodes In K Group?

The optimized O(n) approach using Linked List patterns is generally preferred.

상위 150개 인터뷰쉬움

K 그룹의 역방향 노드

'K 그룹의 역방향 노드' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

연결된 목록의 헤드가 주어지면 목록 k의 노드를 한 번에 반전시키고 수정된 목록을 반환합니다.

k는 양의 정수이고 연결된 목록의 길이보다 작거나 같습니다. 노드의 개수가 k의 배수가 아닌 경우, 남은 노드는 결국 그대로 유지되어야 합니다.

목록 노드의 값은 변경할 수 없으며 노드 자체만 변경할 수 있습니다.

연결된 목록은 Python 목록으로 표시됩니다. reverseKGroup(head: list, k: int) -> list 함수를 구현하세요.

제약

•The number of nodes in the list is n
•1 <= k <= n <= 5000
•0 <= Node.val <= 1000

예

Example 1

Input

[1,2,3,4,5], 2

Output

[2,1,4,3,5]

Explanation

Reverse in groups of 2: [1,2] becomes [2,1], [3,4] becomes [4,3], and [5] stays as is.

Example 2

Input

[1,2,3,4,5], 3

Output

[3,2,1,4,5]

Explanation

Reverse in groups of 3: [1,2,3] becomes [3,2,1], and [4,5] has fewer than 3 nodes so it stays.

Need a Hint?

세트나 힙과 같은 연결 목록 관련 데이터 구조를 사용하는 것을 고려해보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

연결 목록 접근 방식의 논리를 설명하십시오.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def reverse_k_group_opt(head, k: int):
    if isinstance(head, list):
        h = build_linked_list(head)
        res = reverse_k_group_opt_helper(h, k)
        return linked_list_to_list(res)
    return reverse_k_group_opt_helper(head, k)

def reverse_k_group_opt_helper(head: ListNode, k: int) -> ListNode:
    curr = head
    for _ in range(k):
        if not curr:
            return head
        curr = curr.next
    prev = None
    curr = head
    for _ in range(k):
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    head.next = reverse_k_group_opt_helper(curr, k)
    return prev

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def reverse_k_group_brute(head, k: int):
    if isinstance(head, list):
        h = build_linked_list(head)
        res = reverse_k_group_brute_helper(h, k)
        return linked_list_to_list(res)
    return reverse_k_group_brute_helper(head, k)

def reverse_k_group_brute_helper(head: ListNode, k: int) -> ListNode:
    # Recursively reverse k elements by extracting values
    curr = head
    vals = []
    for _ in range(k):
        if not curr: return head
        vals.append(curr.val)
        curr = curr.next
    curr = head
    for v in reversed(vals):
        curr.val = v
        curr = curr.next
    reverse_k_group_brute_helper(curr, k)
    return head