Skip to main content

Leetcode 25: Reverse Nodes in k-Group

 

1. Problem Statement (Simple Explanation):


You’re given the head of a singly linked list and an integer k.

You must:

  • Reverse the nodes of the list k at a time.

  • If the number of nodes at the end is less than k, leave that tail part as is (not reversed).

  • You must not modify node values, only relink nodes.

  • Return the head of the modified list.


2. Examples:


Example 1:

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

Process in groups of 2:

  • Group 1: [1,2] → [2,1]

  • Group 2: [3,4] → [4,3]

  • Remaining node: [5] (less than k) → unchanged

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


Example 2:

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

Process in groups of 3:

  • Group 1: [1,2,3] → [3,2,1]

  • Remaining nodes: [4,5] (less than k) → unchanged

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


Constraints:

  • Number of nodes = n

  • 1 <= k <= n <= 500

  • 0 <= Node.val <= 10000


Follow-up: Solve using O(1) extra space (i.e., in-place, no extra data structures other than a few pointers).


3. Approach – Iterative In-place Reversal in k-Size Groups:


We must reverse nodes in chunks of size k while maintaining links between groups.


High-Level Idea:


  1. Use a dummy node before the head to simplify pointer handling.

  2. Process the list in groups of size k:

    • Find the k-th node starting from the current group’s previous node.

    • If fewer than k nodes remain → stop.

    • Reverse the k nodes between groupPrev.next and kth.

    • Connect the reversed block back to the list.

  3. Move to the next group and repeat.

This works in one pass, reversing in-place with constant extra space.


Key Pointer Roles:


  • dummy: node before the head.

  • groupPrev: node before the current group to reverse.

  • kth: the k-th node ahead from groupPrev (end of the group).

  • groupNext: kth.next (start of the next group after the current one).

Within each group:

  • reverse the segment [groupPrev.next, ..., kth].


Helper: Find k-th Node From groupPrev:



Reversing One Group:


Suppose:

  • groupPrev -> a -> b -> c -> groupNext

    • (head of group)      (kth.next)

After reversing group [a,b,c]:

  • groupPrev -> c -> b -> a -> groupNext

Process:

  1. prev = groupNext (so tail connects correctly).

  2. curr = groupPrev.next (head of group before reversing).

  3. While curr != groupNext:

    • tmp = curr.next

    • curr.next = prev

    • prev = curr

    • curr = tmp

  4. After this, prev is the new head of the group (old kth).

  5. Old head groupPrev.next becomes the tail of the group.

Connect:

  • tail = groupPrev.next

  • groupPrev.next = prev

  • groupPrev = tail for the next iteration.


Pseudo-code (Iterative, O(1) Extra Space):



This is in-place and uses only a fixed number of extra pointers - O(1) extra space.


Complexity:


Let n be number of nodes:

  • Each node is visited and relinked a constant number of times.

  • Time: O(n)

  • Extra space: O(1)  (follow-up satisfied).


4. Java code:



5. C code:



6. C++ code:



7. Python code:



8. JavaScript code:




Comments

Post a Comment

Popular posts from this blog

Leetcode 1: Two Sum

  Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to  return the indices of two numbers in the array  such that: Conditions: Each input has  exactly one solution . You  cannot use the same element twice . You can return the answer in  any order . 2. Examples Example 1 Input:                                    nums = [2, 7, 11, 15], target = 9 Output:                                 [0, 1] Explanation:                     nums[0]+nums[1]=2+7=9              So we return [0, 1]. Example 2 Input:           ...
Post a Comment
Read more

Leetcode 3: Longest Substring Without Repeating Characters

  Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not  contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input:   s = "pwwkew" Output:   3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...
Post a Comment
Read more

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given  two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a  single digit . The digits are stored in  reverse order  (i.e., the 1’s digit is at the head). You need to  add the two numbers  and return the  sum as a linked list , also in reverse order. You can assume: There are  no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input:                l1 = [2,4,3]                l2 = [5,6,4]           Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output:                [7,0,8] Explanation:        ...
Post a Comment
Read more