25. Reverse nodes groups

25_solution1_iterative.c

#include "list_node.h"

struct ListNode *reverseKGroup(struct ListNode *head, int k) {
  struct ListNode dummy = {0, head};
  struct ListNode *groupPrev = &dummy;

  for (;;) {
    // find the k-th node of this group
    struct ListNode *kth = groupPrev;
    for (int i = 0; i < k && kth; i++)
      kth = kth->next;
    if (!kth)
      break; // fewer than k nodes left

    struct ListNode *groupStart = groupPrev->next;
    struct ListNode *groupNext = kth->next; // first node after the group

    // reverse k nodes, starting with prev = groupNext so the
    // old head ends up pointing to the rest of the list
    struct ListNode *prev = groupNext;
    struct ListNode *cur = groupStart;
    while (cur != groupNext) {
      struct ListNode *next = cur->next;
      cur->next = prev;
      prev = cur;
      cur = next;
    }

    groupPrev->next = kth;  // previous part -> new group head
    groupPrev = groupStart; // old head is now the group's tail
  }

  return dummy.next;
}

25_solution2_recursion.c

#include "list_node.h"

struct ListNode *reverseKGroup(struct ListNode *head, int k) {
  // check that k nodes exist
  struct ListNode *node = head;
  for (int i = 0; i < k; i++) {
    if (!node)
      return head; // fewer than k: leave as is
    node = node->next;
  }
  // node is now the (k+1)-th node, i.e. the start of the rest

  struct ListNode *prev = reverseKGroup(node, k); // already-processed rest
  struct ListNode *cur = head;
  for (int i = 0; i < k; i++) {
    struct ListNode *next = cur->next;
    cur->next = prev;
    prev = cur;
    cur = next;
  }
  return prev; // new head of this group
}

list_node.h

#pragma once

#include <stddef.h>

// Definition for singly-linked list.
struct ListNode {
  int val;
  struct ListNode *next;
};

25_solution1_iterative.cpp

#include "list_node.h"

class Solution {
public:
  ListNode *reverseKGroup(ListNode *head, int k) {
    ListNode dummy(0, head);
    ListNode *groupPrev = &dummy;

    for (;;) {
      // find the k-th node of this group
      ListNode *kth = groupPrev;
      for (int i = 0; i < k && kth; i++)
        kth = kth->next;
      if (!kth)
        break; // fewer than k nodes left

      ListNode *groupStart = groupPrev->next;
      ListNode *groupNext = kth->next; // first node after the group

      // reverse k nodes, starting with prev = groupNext so the
      // old head ends up pointing to the rest of the list
      ListNode *prev = groupNext;
      ListNode *cur = groupStart;
      while (cur != groupNext) {
        ListNode *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
      }

      groupPrev->next = kth;  // previous part -> new group head
      groupPrev = groupStart; // old head is now the group's tail
    }

    return dummy.next;
  }
};

25_solution2_recursion.cpp

#include "list_node.h"

class Solution {
public:
  ListNode *reverseKGroup(ListNode *head, int k) {
    // check that k nodes exist
    ListNode *node = head;
    for (int i = 0; i < k; i++) {
      if (!node)
        return head; // fewer than k: leave as is
      node = node->next;
    }
    // node is now the (k+1)-th node, i.e. the start of the rest

    ListNode *prev = reverseKGroup(node, k); // already-processed rest
    ListNode *cur = head;
    for (int i = 0; i < k; i++) {
      ListNode *next = cur->next;
      cur->next = prev;
      prev = cur;
      cur = next;
    }
    return prev; // new head of this group
  }
};

list_node.h

#pragma once

// Definition for singly-linked list.
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};

25_solution1_iterative.go

package linkedlists

func reverseKGroup(head *ListNode, k int) *ListNode {
    dummy := &ListNode{Next: head}
    groupPrev := dummy

    for {
        // find the k-th node of this group
        kth := groupPrev
        for i := 0; i < k && kth != nil; i++ {
            kth = kth.Next
        }
        if kth == nil {
            break // fewer than k nodes left
        }

        groupStart := groupPrev.Next
        groupNext := kth.Next // first node after the group

        // reverse k nodes, starting with prev = groupNext so the
        // old head ends up pointing to the rest of the list
        prev := groupNext
        cur := groupStart
        for cur != groupNext {
            next := cur.Next
            cur.Next = prev
            prev = cur
            cur = next
        }

        groupPrev.Next = kth   // previous part -> new group head
        groupPrev = groupStart // old head is now the group's tail
    }

    return dummy.Next
}

25_solution2_recursion.go

package linkedlists

func reverseKGroup(head *ListNode, k int) *ListNode {
    // check that k nodes exist
    node := head
    for i := 0; i < k; i++ {
        if node == nil {
            return head // fewer than k: leave as is
        }
        node = node.Next
    }
    // node is now the (k+1)-th node, i.e. the start of the rest

    prev := reverseKGroup(node, k) // already-processed rest
    cur := head
    for i := 0; i < k; i++ {
        next := cur.Next
        cur.Next = prev
        prev = cur
        cur = next
    }
    return prev // new head of this group
}

list_node.go

package linkedlists

// Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

25_solution1_iterative.java

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode groupPrev = dummy;

        while (true) {
            // find the k-th node of this group
            ListNode kth = groupPrev;
            for (int i = 0; i < k && kth != null; i++)
                kth = kth.next;
            if (kth == null)
                break; // fewer than k nodes left

            ListNode groupStart = groupPrev.next;
            ListNode groupNext = kth.next; // first node after the group

            // reverse k nodes, starting with prev = groupNext so the
            // old head ends up pointing to the rest of the list
            ListNode prev = groupNext;
            ListNode cur = groupStart;
            while (cur != groupNext) {
                ListNode next = cur.next;
                cur.next = prev;
                prev = cur;
                cur = next;
            }

            groupPrev.next = kth; // previous part -> new group head
            groupPrev = groupStart; // old head is now the group's tail
        }

        return dummy.next;
    }
}

25_solution2_recursion.java

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // check that k nodes exist
        ListNode node = head;
        for (int i = 0; i < k; i++) {
            if (node == null)
                return head; // fewer than k: leave as is
            node = node.next;
        }
        // node is now the (k+1)-th node, i.e. the start of the rest

        ListNode prev = reverseKGroup(node, k); // already-processed rest
        ListNode cur = head;
        for (int i = 0; i < k; i++) {
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        return prev; // new head of this group
    }
}

ListNode.java

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;

    ListNode() {}

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

25_solution1_iterative.js

const ListNode = require("./list_node");

var reverseKGroup = function (head, k) {
  const dummy = new ListNode(0, head);
  let groupPrev = dummy;

  for (;;) {
    // find the k-th node of this group
    let kth = groupPrev;
    for (let i = 0; i < k && kth !== null; i++) kth = kth.next;
    if (kth === null) break; // fewer than k nodes left

    const groupStart = groupPrev.next;
    const groupNext = kth.next; // first node after the group

    // reverse k nodes, starting with prev = groupNext so the
    // old head ends up pointing to the rest of the list
    let prev = groupNext;
    let cur = groupStart;
    while (cur !== groupNext) {
      const next = cur.next;
      cur.next = prev;
      prev = cur;
      cur = next;
    }

    groupPrev.next = kth; // previous part -> new group head
    groupPrev = groupStart; // old head is now the group's tail
  }

  return dummy.next;
};

25_solution2_recursion.js

const ListNode = require("./list_node");

var reverseKGroup = function (head, k) {
  // check that k nodes exist
  let node = head;
  for (let i = 0; i < k; i++) {
    if (node === null) return head; // fewer than k: leave as is
    node = node.next;
  }
  // node is now the (k+1)-th node, i.e. the start of the rest

  let prev = reverseKGroup(node, k); // already-processed rest
  let cur = head;
  for (let i = 0; i < k; i++) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }
  return prev; // new head of this group
};

list_node.js

// Definition for singly-linked list.
function ListNode(val, next) {
  this.val = val === undefined ? 0 : val;
  this.next = next === undefined ? null : next;
}

module.exports = ListNode;

25_solution1_iterative.py

from typing import Optional

from list_node import ListNode


class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        group_prev = dummy

        while True:
            # find the k-th node of this group
            kth = group_prev
            for _ in range(k):
                if not kth:
                    break
                kth = kth.next
            if not kth:
                break  # fewer than k nodes left

            group_start = group_prev.next
            group_next = kth.next  # first node after the group

            # reverse k nodes, starting with prev = group_next so the
            # old head ends up pointing to the rest of the list
            prev = group_next
            cur = group_start
            while cur != group_next:
                nxt = cur.next
                cur.next = prev
                prev = cur
                cur = nxt

            group_prev.next = kth  # previous part -> new group head
            group_prev = group_start  # old head is now the group's tail

        return dummy.next

25_solution2_recursion.py

from typing import Optional

from list_node import ListNode


class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # check that k nodes exist
        node = head
        for _ in range(k):
            if not node:
                return head  # fewer than k: leave as is
            node = node.next
        # node is now the (k+1)-th node, i.e. the start of the rest

        prev = self.reverseKGroup(node, k)  # already-processed rest
        cur = head
        for _ in range(k):
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        return prev  # new head of this group

list_node.py

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

25_solution1_iterative.rs

use crate::list_node::ListNode;

impl Solution {
    pub fn reverse_k_group(head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
        let k = k as usize;

        let mut len = 0;
        let mut p = &head;
        while let Some(node) = p {
            len += 1;
            p = &node.next;
        }

        let mut dummy = Box::new(ListNode::new(0));
        dummy.next = head;
        let mut tail = &mut dummy;

        for _ in 0..len / k {
            // reverse the k nodes after tail
            let mut cur = tail.next.take();
            let mut prev = None;
            for _ in 0..k {
                let mut node = cur.unwrap();
                cur = node.next.take();
                node.next = prev;
                prev = Some(node);
            }
            tail.next = prev;

            // old head is now the group's tail; reattach the rest
            for _ in 0..k {
                tail = tail.next.as_mut().unwrap();
            }
            tail.next = cur;
        }

        dummy.next
    }
}

25_solution2_recursion.rs

use crate::list_node::ListNode;

impl Solution {
    pub fn reverse_k_group(head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
        let k = k as usize;

        // check that k nodes exist
        let mut p = &head;
        for _ in 0..k {
            match p {
                None => return head, // fewer than k: leave as is
                Some(node) => p = &node.next,
            }
        }

        // detach the rest after the k-th node
        let mut head = head;
        let mut p = &mut head;
        for _ in 0..k {
            p = &mut p.as_mut().unwrap().next;
        }
        let rest = p.take();

        let mut prev = Self::reverse_k_group(rest, k as i32); // already-processed rest
        let mut cur = head;
        while let Some(mut node) = cur {
            cur = node.next.take();
            node.next = prev;
            prev = Some(node);
        }
        prev // new head of this group
    }
}

list_node.rs

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        ListNode { val, next: None }
    }
}