Katkat
Back

Reverse a Linked List in Groups of K

ByteDanceMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate pointers in a linked list structure and manage iterative or recursive state transitions for fixed-size segments.

Reverse a Linked List in Groups of K

You are given a singly linked list and an integer k. You need to reverse the nodes of the list k at a time and return the modified list. If the number of nodes is not a multiple of k, the left-out nodes at the end should remain as they are.

Function Signature

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseKGroup(head: ListNode, k: int) -> ListNode:
    # implementation here

Constraints

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

Examples

Example 1: Input: head = [1, 2, 3, 4, 5], k = 2 Output: [2, 1, 4, 3, 5] Explanation: The first two nodes (1, 2) are reversed, the next two (3, 4) are reversed, and the final node (5) stays as is.

Example 2: Input: head = [1, 2, 3, 4, 5], k = 3 Output: [3, 2, 1, 4, 5] Explanation: The first three nodes (1, 2, 3) are reversed, and the remaining nodes (4, 5) are less than 3, so they remain unchanged.

Edge Cases

  • k = 1: The list should remain unchanged.
  • The list length is exactly k.
  • The list length is less than k.
  • An empty list (head is None).

Hints

Hint 1

Check if there are at least k nodes remaining in the list before attempting to reverse a group.

Hint 2

Use a dummy head node to simplify the connection logic between the end of the previous reversed group and the start of the next.

Hint 3

Consider an iterative approach using two pointers to reverse the segments in-place without using extra space proportional to the list size.

Follow-up questions

  • How would you modify your solution to reverse the groups only if the total number of nodes is a multiple of k?
  • What is the space complexity of your solution? Can you achieve O(1) auxiliary space even if using recursion?
  • If the linked list were doubly linked, what additional pointer updates would be required during the reversal of each group?