Reversing Linked List Nodes in Groups of K

Linked lists are a pretty fun data structure to work with. They’re able to eject elements in O(1) time without all the drama that arrays are subject to. Combined with hashmaps, they empower us to execute fast operations for a variety of use cases (LRU cache, anyone?).

Every CS student learns to reverse a linked list at some point in their studies. Today, we’ll visit a version of this problem that comes with a twist.

From LeetCode:

Reverse the nodes of a linked list, k at a time, and return the modified list.

k is a positive integer. It is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k, any left-out nodes at the end should remain as they are.

Input:  head = 1 -> 2 -> 3 -> 4 -> 5, k = 2
Output: 2 -> 1 -> 4 -> 3 -> 5

Input:  head = 1 -> 2 -> 3 -> 4 -> 5, k = 3
Output: 3 -> 2 -> 1 -> 4 -> 5

Notes:

• Only constant extra memory is allowed.
• You may not alter the values in the list’s nodes, only nodes themselves may be changed.

Determining the Number of Groups

Since we know that the nodes are reversed in groups of k, the first question we might want to answer is: How many groups exactly? We’ll determine the length of the list with a single pass and divide this length by k.

def reverse_list_in_groups_of_k(head, k):

    sentinel = runner = Node()

    length = 0
    while runner.next:
      runner = runner.next
      length += 1

    num_groups = length // k
  
    # ...

Notice that I’ve prepended a sentinel node to the linked list. This practice turns out to be useful in many list-related problems, especially when your algorithm is likely to modify pointers on the head node.

Reversing a Sublist

Now that we’ve determined the number of groups (num_groups), we’ll need to outline the subroutine for reversing a single group of k.

Think about how a linked list is normally reversed:

Before: 1 -> 2 -> 3 -> 4 -> 5
After:  5 -> 4 -> 3 -> 2 -> 1 

This is seems pretty easy, but what if we needed to update a sublist, such as the middle nodes 2 -> 3 -> 4?

Before: 1 -> 2 -> 3 -> 4 -> 5
After:  1 -> 4 -> 3 -> 2 -> 5
#            |---------|
#                 |
#           flipped sublist

Doing this is tricker, because we need flip the sublist and update the pointers at the boundaries.

My approach for handling this involves the maintenance of three pointers: prehead, backrunner, and frontrunner, which are tagged as p , b, and f respectively in the snippet below:

# Initial State
List: 1 -> 2 -> 3 -> 4 -> 5
#     p    b    f

To clarify, prehead points to the node before the head of the sublist. backrunner and frontrunner are the two runners that will be responsible for flipping the nodes inside the sublist.

We’ll first allow backrunner and frontrunner flip pairs of nodes k-1 times. For 2 -> 3 -> 4, this means two times: First with 2 -> 3, then with 3 -> 4.

# Initial State
List: 1 -> 2 -> 3 -> 4 -> 5
#     p    b    f

# After 1st flip
List: 1 -> 2 <- 3 -> 4 -> 5
#     p         b    f

# After 2nd flip
List: 1 -> 2 <- 3 <- 4 -> 5
#     p              b    f

Once the nodes inside the sublist have been updated, we’ll need to update the pointers between the boundaries of the sublist and the main list. At this stage:

• prehead still points to the node before the head of the sublist
• backrunner points to the tail of the sublist
• frontrunner points to the node after the tail of the sublist

Our next steps are simple. We want:

• prehead’s next node’s (i.e. the sublist head’s) next pointer to be directed to the frontrunner
• prehead’s next pointer to be directed to the backrunner

# After 2nd flip
List: 1 -> 2 <- 3 <- 4 -> 5
#     p              b    f

# After updating boundary nodes
List: 1 -> 4 -> 3 -> 2 -> 5
#     p    b              f

If we were to express the above in code:

# Setup
prehead = runner
backrunner, frontrunner = runner.next, runner.next.next

# Flipping nodes inside the sublist
for _ in range(k-1):
    frontrunner_next = frontrunner.next
    frontrunner.next = backrunner
    backrunner, frontrunner = frontrunner, frontrunner_next

# Updating the sublist's boundaries
prehead.next.next = frontrunner
runner = prehead.next
prehead.next = backrunner

Once we’re done reversing the sublist, we set up the next reversal by updating runner to prehead.next. This is because prehead.next is the node that precedes the head of the next sublist!

Reversing the Groups

Having figured out how to reverse a sublist, the rest of the algorithm becomes somewhat straightforward. All we have to do is to run these sublist reversals num_groups number of times.

def reverse_list_in_groups_of_k(head, k):
    # Get length
    # ...
    
    # Determine number of groups
    num_groups = length // k

    # Reset runner
    runner = sentinel
        
    for _ in range(num_groups):
        # Run sublist reversal
        # ...

    return sentinel.next

Given n number of nodes, our algorithm runs in O(1) space and O(n) time.

With that, we’ve solved the Reverse Linked List Nodes in Groups of K problem 💞💞💞.

Full Solution

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

def reverse_list_in_groups_of_k(head, k):
    runner = sentinel = ListNode(None)
    sentinel.next = head
    
    # Get length
    length = 0
    while runner.next:
        runner = runner.next 
        length += 1
    
    # Determine number of groups
    num_groups = length // k

    # Reset runner
    runner = sentinel
        
    for _ in range(num_groups):
        prehead = runner
        backrunner, frontrunner = runner.next, runner.next.next
        
        for _ in range(k-1):
            frontrunner_next = frontrunner.next
            frontrunner.next = backrunner
            backrunner, frontrunner = frontrunner, frontrunner_next
        

        prehead.next.next = frontrunner
        runner = prehead.next
        prehead.next = backrunner
    
    return sentinel.next