20. Reverse Nodes in k-Group

IMP

Given a linked list, reverse the nodes of a linked list k at a time and return its 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.

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]

Example 3:

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

Example 4:

Input: head = [1], k = 1
Output: [1]

Solution:

Approach:

Adding a prenode and changing 3 pointers

-1 -> 1 -> 2 -> 3 -> 4 -> 5
 |    |    |    | 
pre  cur  nex  tmp

-1 -> 2 -> 1 -> 3 -> 4 -> 5
 |         |    |    | 
pre       cur  nex  tmp

-1 -> 3 -> 2 -> 1 -> 4 -> 5
 |              |    |    | 
pre            cur  nex  tmp

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) {}
  };
 
class Solution
{
public:
    ListNode *reverseKGroup(ListNode *head, int k)
    {

        if (head == NULL || k == 1)
        {
            return head;
        }
        ListNode *p = head;
        int count = 0;
        while (p != NULL)
        {
            p = p->next;
            count++;
        }
        ListNode *prenode = new ListNode;
        prenode->val = -1;
        prenode->next = head;
        ListNode *pre = prenode;
        ListNode *cur = prenode;
        ListNode *nxt = prenode;
        ListNode *temp = NULL;

        while (count >= k)
        {
            cur = pre->next;
            nxt = cur->next;

            for (int i = 1; i < k; i++)
            {
                temp = nxt->next;
                nxt->next = pre->next;
                pre->next = nxt;
                cur->next = temp;
                nxt = temp;
            }
            count -= k;
            pre = cur;
        }

        return prenode->next;
    }
};

Time Complexity: O(n) Space Complexity: O(1)