Problem statement (Leetcode Hard)

• You are given the head of a singly linked list head and a positive integer k.
• You must reverse the first k nodes in the linked list, and then reverse the next k nodes, and so on. If there are fewer than k nodes left, leave the nodes as they are.
• Return the modified list after reversing the nodes in each group of k.
• You are only allowed to modify the nodes' next pointers, not the values of the nodes.

Solution (recursion)

(I had such a hard time trying to do this iteratively... the recursion version makes muuuch more sense.)

public class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode cur = head;
        int group = 0;
        while (cur != null && group < k) {
            cur = cur.next;
            group++;
        }

        if (group == k) {
            cur = reverseKGroup(cur, k);
            while (group-- > 0) {
                ListNode tmp = head.next;
                head.next = cur;
                cur = head;
                head = tmp;
            }
            head = cur;
        }
        return head;
    }
}

Strategy

• The cur value returned from reverseKGroup(cur,k) will be already reversed and be ready for you.
• In the reversing while loop
  • head -> the next node we want to reverse
  • cur -> the "end node" that we will connect head.next
• The head = cur after the while loop
  • in the end, ListNode tmp = head.next will be the last element (the very first initial cur that we got from recursion)
  • and cur will be at the beginning
  • so we set head = cur to return the head for next iteration (from the recursion).. or we can also just simple return cur

Time complexity

• O(N)
  • in the first visit, we check each node(k steps) to check if there are enough nodes.
  • Then inside the if (group == k) block, the head pointer iterates through those same k nodes.
  • So roughly the total operations are O(2N), but it's reduced to O(N).