PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates linked list manipulation, pointer/reference management, in-place iterative algorithms, and the ability to enforce O(1) extra space constraints.

  • medium
  • Bytedance
  • Coding & Algorithms
  • Software Engineer

Reverse Linked List Groups

Company: Bytedance

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Given the head of a singly linked list and a positive integer `k`, reverse the list in consecutive groups of size `k`. Unlike the common variant where a final group with fewer than `k` nodes is left unchanged, in this problem the final remaining group must also be reversed, even if it contains fewer than `k` nodes. For example: - Input: `1 -> 2 -> 3 -> 4 -> 5`, `k = 2` - Output: `2 -> 1 -> 4 -> 3 -> 5` - Input: `1 -> 2 -> 3 -> 4 -> 5`, `k = 3` - Output: `3 -> 2 -> 1 -> 5 -> 4` Assume the linked list node is defined as `ListNode { val, next }`. The input guarantees `k <= length of the list`. Implement the function using an iterative approach with `O(1)` extra space. Do not copy node values into an array or use an auxiliary stack. Follow-up questions: 1. What happens when `k = 1`? 2. If the guarantee `k <= length` were removed, how would you handle `k > length`? 3. What are the time and space complexities of your algorithm?

Quick Answer: This question evaluates linked list manipulation, pointer/reference management, in-place iterative algorithms, and the ability to enforce O(1) extra space constraints.

Part 1: Reverse Linked List in Groups Including the Final Partial Group

Given the values of a singly linked list and a positive integer k, reverse the linked list in consecutive groups of size k. Unlike the common k-group reversal variant, the final remaining group must also be reversed even if it contains fewer than k nodes. For this runnable problem, the linked list is provided as a Python list of node values, and you must return the resulting node values. The intended algorithm should rewire linked-list pointers iteratively; do not solve the core reversal by slicing the Python list, copying values into another array, or using a stack.

Constraints

  • 1 <= len(values) <= 10^5
  • 1 <= k <= len(values)
  • -10^9 <= values[i] <= 10^9
  • The core linked-list reversal must be iterative.
  • Use O(1) auxiliary space for pointer manipulation, excluding the input/output serialization used by this problem.

Examples

Input: ([1, 2, 3, 4, 5], 2)

Expected Output: [2, 1, 4, 3, 5]

Explanation: Groups are [1,2], [3,4], and [5]. Each group is reversed.

Input: ([1, 2, 3, 4, 5], 3)

Expected Output: [3, 2, 1, 5, 4]

Explanation: The final partial group [4,5] is reversed to [5,4].

Input: ([7], 1)

Expected Output: [7]

Explanation: Single-node list with k = 1 remains unchanged.

Input: ([1, 2, 3, 4], 4)

Expected Output: [4, 3, 2, 1]

Explanation: When k equals the list length, the whole list is one reversed group.

Hints

  1. Reverse one group at a time, keeping track of the tail of the previously processed group.
  2. When a group ends early because the list runs out, reverse the nodes you have anyway instead of restoring them.

Part 2: Behavior of K-Group Reversal When k = 1

Given the values of a singly linked list, determine the result of reversing the list in consecutive groups when k is fixed to 1. Since each group contains exactly one node, reversing each group should preserve the original order. For this runnable problem, the linked list is represented by a list of node values.

Constraints

  • 0 <= len(values) <= 10^5
  • -10^9 <= values[i] <= 10^9
  • k is fixed to 1.
  • The relative order of all nodes must remain unchanged.

Examples

Input: ([1, 2, 3, 4],)

Expected Output: [1, 2, 3, 4]

Explanation: Each group has one node, so the list is unchanged.

Input: ([],)

Expected Output: []

Explanation: An empty list remains empty.

Input: ([42],)

Expected Output: [42]

Explanation: A single node remains unchanged.

Input: ([-1, 0, -1, 5],)

Expected Output: [-1, 0, -1, 5]

Explanation: Values and order are preserved exactly.

Hints

  1. A one-element group is identical before and after reversal.
  2. Think about whether any pointer rewiring is necessary for a single-node group.

Part 3: Reverse Linked List Groups When k May Exceed the List Length

Given the values of a singly linked list and a positive integer k, reverse the list in consecutive groups of size k. The guarantee k <= length of the list has been removed. If k is greater than the list length, the entire list is treated as one final partial group and must be reversed. If the list is empty, return an empty list. For this runnable problem, the linked list is provided as a Python list of node values, and you must return the resulting node values. The intended algorithm should rewire linked-list pointers iteratively and should not rely on array slicing or an auxiliary stack.

Constraints

  • 0 <= len(values) <= 10^5
  • 1 <= k <= 10^9
  • -10^9 <= values[i] <= 10^9
  • The core linked-list reversal must be iterative.
  • Use O(1) auxiliary space for pointer manipulation, excluding input/output serialization.

Examples

Input: ([1, 2, 3], 5)

Expected Output: [3, 2, 1]

Explanation: k is larger than the list length, so the whole list is one partial group and is reversed.

Input: ([1, 2, 3, 4, 5], 2)

Expected Output: [2, 1, 4, 3, 5]

Explanation: Regular groups of size 2 are reversed, and the final single-node group remains itself.

Input: ([], 3)

Expected Output: []

Explanation: The empty list remains empty.

Input: ([9], 10)

Expected Output: [9]

Explanation: A single-node list is unchanged even though k is greater than the length.

Input: ([1, 2, 3, 4], 4)

Expected Output: [4, 3, 2, 1]

Explanation: When k equals the length, the entire list is reversed.

Hints

  1. You do not need to precompute the length to handle k > length.
  2. Start reversing a group and stop either after k nodes or when you reach the end of the list.

Part 4: Determine Complexity of Iterative K-Group Linked List Reversal

You are analyzing the iterative in-place algorithm that reverses a singly linked list in consecutive groups of size k, including the final partial group. Given n, the number of nodes, and k, return a compact complexity report. Use this model: the algorithm processes every node exactly once, uses only a constant number of pointer variables, creates ceil(n / k) non-empty groups when n > 0, performs one internal next-pointer write per node while reversing, and performs one additional group-connection next-pointer write per non-empty group. Return the number of groups, the modeled number of next-pointer writes, and the asymptotic time and auxiliary space classes.

Constraints

  • 0 <= n <= 10^18
  • 1 <= k <= 10^18
  • Use integer arithmetic; do not simulate the linked list.
  • The reported asymptotic complexities are for the iterative linked-list reversal algorithm.

Examples

Input: (5, 2)

Expected Output: ['groups=3', 'pointer_writes=8', 'time=O(n)', 'space=O(1)']

Explanation: The groups are sizes 2, 2, and 1. Pointer writes are 5 node reversals plus 3 group connections.

Input: (5, 3)

Expected Output: ['groups=2', 'pointer_writes=7', 'time=O(n)', 'space=O(1)']

Explanation: The groups are sizes 3 and 2.

Input: (1, 1)

Expected Output: ['groups=1', 'pointer_writes=2', 'time=O(n)', 'space=O(1)']

Explanation: One node forms one group.

Input: (0, 4)

Expected Output: ['groups=0', 'pointer_writes=0', 'time=O(n)', 'space=O(1)']

Explanation: An empty list has no groups and no pointer writes.

Input: (10, 20)

Expected Output: ['groups=1', 'pointer_writes=11', 'time=O(n)', 'space=O(1)']

Explanation: When k > n, the whole non-empty list is one partial group.

Hints

  1. Every node is visited and reversed once, regardless of k.
  2. The number of groups is ceil(n / k), except that an empty list has zero groups.
Last updated: Jun 13, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Reverse Nodes in K-Sized Groups - Bytedance
  • Solve Bracket Matching and Tree Width - Bytedance (hard)
  • Solve Stack and String Shift Problems - Bytedance (medium)
  • Find LCA With Parent Pointers - Bytedance (medium)
  • Count Target-Sum Paths in an N-ary Tree - Bytedance (hard)