Question

Formatted question description: https://leetcode.ca/all/25.html

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list's nodes, only nodes themselves may be changed.

Example 1:

Input: head = [1,2,3,4,5], k = 2
Output: [2,1,4,3,5]

Example 2:

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

Constraints:

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

Follow-up: Can you solve the problem in O(1) extra memory space?

Algorithm

To reverse a linked list in groups of size k, we first need to divide the original linked list into several small segments, each containing k nodes, and then flip each segment separately. This requires two functions, one for segmentation and one for flipping.

For example, consider the linked list 1->2->3->4->5. When dealing with linked list problems, it’s common to add a dummy node at the beginning because the head node may change when the linked list is flipped. To keep track of the current latest position of the head node, we introduce a dummy node before the original head node. In this case, the linked list after adding the dummy node becomes -1->1->2->3->4->5.

To reverse the group of nodes 1, 2, and 3 when k is 3, we need two pointers: pre and next. pre points to the node before the group to be flipped, and next points to the node after the group to be flipped. After flipping the group, the position of pre is updated to the following new position.

prev is dummy, then current is always node ‘1’, ‘1’ will move each iteration of while loop for k-group swap

prev is static during the full while loop of while (kcopy > 0)

1->2->3->4->5 , k=3

2,1,3,4,5
3,2,1,4,5
=> always getting 1's next for prev's next => current (below) not changing in one-batch-swap

Code

public class Reverse_Nodes_in_k_Group {

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

            ListNode prev = dummy;

            // count total nodes
            ListNode tmp = head;
            int count = 0;
            while (tmp != null) {
                count++;
                tmp = tmp.next;
            }

            // 1->2->3->4->5 , k=3
            // 2,1,3,4,5
            // 3,2,1,4,5
            // => always getting 1's next for prev's next => current (below) not changing in one-batch-swap

            // if only one node left, then no swap
            while (count >= k) {

                ListNode originalFirst = prev.next;

                int kcopy = k - 1; // @note: since current node is already counted as 1
                while (kcopy > 0) { // both prev and current, not changed in while loop

                    ListNode nextNextCopy = originalFirst.next.next;
                    ListNode firstInGroup = prev.next;

                    prev.next = originalFirst.next;
                    prev.next.next = firstInGroup;
                    originalFirst.next = nextNextCopy;

                    kcopy--;
                }

                // @note: update previous AND current. I forgot current...
                prev = originalFirst; // now current is the last one of this group
                count -= k;
            }

            return dummy.next;
        }
    }
}

// OJ: https://leetcode.com/problems/reverse-nodes-in-k-group/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode h, *tail = &h;
        while (head) {
            auto prev = tail;
            int i = 0;
            for (auto p = head; i < k && p; ++i, p = p->next);
            if (i < k) {
                tail->next = head;
                break;
            }
            for (int i = 0; i < k && head; ++i) {
                auto node = head;
                head = head->next;
                node->next = prev->next;
                prev->next = node;
            }
            while (tail->next) tail = tail->next;
        }
        return h.next;
    }
};

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        def reverseList(head):
            pre, p = None, head
            while p:
                q = p.next
                p.next = pre
                pre = p
                p = q
            return pre

        dummy = ListNode(next=head)
        pre = cur = dummy
        while cur.next:
            for _ in range(k):
                cur = cur.next
                if cur is None:
                    return dummy.next
            t = cur.next
            cur.next = None # cut from next k-group, so to reverseList() for current k-group
            start = pre.next
            pre.next = reverseList(start)
            start.next = t # so now 'start' is the last node of k-group
            pre = cur = start # same as the reset before while loop
        return dummy.next

############

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

class Solution(object):
  def reverseKGroup(self, head, k):
    """
    :type head: ListNode
    :type k: int
    :rtype: ListNode
    """

    def reverseList(head, k):
      pre = None
      cur = head
      while cur and k > 0:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
        k -= 1
      head.next = cur
      return cur, pre

    length = 0
    p = head
    while p:
      length += 1
      p = p.next
    if length < k:
      return head
    step = length / k
    ret = None
    pre = None
    p = head
    while p and step:
      next, newHead = reverseList(p, k)
      if ret is None:
        ret = newHead
      if pre:
        pre.next = newHead
      pre = p
      p = next
      step -= 1
    return ret

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
	start, end := head, head
	for i := 0; i < k; i++ {
		if end == nil {
			return head
		}
		end = end.Next
	}
	res := reverse(start, end)
	start.Next = reverseKGroup(end, k)
	return res
}

func reverse(start, end *ListNode) *ListNode {
	var pre *ListNode = nil
	for start != end {
		tmp := start.Next
		start.Next, pre = pre, start
		start = tmp
	}
	return pre
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
    let dummy = new ListNode(0, head);
    let pre = dummy;
    // pre->head-> ... ->tail-> next
    while (head != null) {
        let tail = pre;
        for (let i = 0; i < k; ++i) {
            tail = tail.next;
            if (tail == null) {
                return dummy.next;
            }
        }
        let t = tail.next;
        [head, tail] = reverse(head, tail);
        // set next
        pre.next = head;
        tail.next = t;
        // set new pre and new head
        pre = tail;
        head = t;
    }
    return dummy.next;
}

function reverse(head: ListNode, tail: ListNode) {
    let cur = head;
    let pre = tail.next;
    // head -> next -> ... -> tail -> pre
    while (pre != tail) {
        let t = cur.next;
        cur.next = pre;
        pre = cur;
        cur = t;
    }
    return [tail, head];
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode ReverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode pre = dummy, cur = dummy;
        while (cur.next != null)
        {
            for (int i = 0; i < k && cur != null; ++i)
            {
                cur = cur.next;
            }
            if (cur == null)
            {
                return dummy.next;
            }
            ListNode t = cur.next;
            cur.next = null;
            ListNode start = pre.next;
            pre.next = ReverseList(start);
            start.next = t;
            pre = start;
            cur = pre;
        }
        return dummy.next;
    }

    private ListNode ReverseList(ListNode head) {
        ListNode pre = null, p = head;
        while (p != null)
        {
            ListNode q = p.next;
            p.next = pre;
            pre = p;
            p = q;
        }
        return pre;
    }
}

25 - Reverse Nodes in k-Group

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions