Reverse Nodes in k-Group

LeetCode 25 | Difficulty: Hard

Hard

Problem Description

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?

Topics: Linked List, Recursion

---

Approach

Linked List

Use pointer manipulation. Common techniques: dummy head node to simplify edge cases, fast/slow pointers for cycle detection and middle finding, prev/curr/next pattern for reversal.

When to use

In-place list manipulation, cycle detection, merging lists, finding the k-th node.

---

Solutions

Solution 1: C# (Best: 185 ms)

Metric	Value
Runtime	185 ms
Memory	N/A
Date	2017-08-07

Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode ReverseKGroup(ListNode head, int k) {
    if(head==null || k == 1) return head;
    int num=0;
    var preheader = new ListNode(Int32.MaxValue);
    preheader.next = head;
    ListNode pre = preheader, nex, current = preheader;
    while (current.next != null)
    {
        num++;
        current = current.next;
    }

    while (num >= k)
    {
        current = pre.next;
        nex = current.next;
        for (int i = 1; i < k; i++)
        {
            current.next = nex.next;
            nex.next = pre.next;
            pre.next = nex;
            nex = current.next;
        }
        pre = current;
        num -= k;
    }

    return preheader.next;
    }
}

---

Complexity Analysis

Approach	Time	Space
Linked List	$O(n)$	$O(1)$

---

Interview Tips

Key Points

• Break the problem into smaller subproblems. Communicate your approach before coding.
• Draw the pointer changes before coding. A dummy head node simplifies edge cases.