Leetcode 25 Solution

This article provides solution to leetcode question 25 (reverse-nodes-in-k-group)
Categories:
Tags:
Access this page by simply typing in "lcs 25" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/reverse-nodes-in-k-group

Thinking Process

This question requires you to carefully manipulate the nodes in the list to finish the reverse process. There is no complicated algorithm in it.

Be sure to leverage the dummy head trick to keep the code clean.

Time & Space Complexity

Assuming there are N nodes in the list:

  • Time complexity: O(N)
  • Space complexity: O(1)

Solution

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode dummyNode(0);
        dummyNode.next = head;

        ListNode* prev = &dummyNode;
        ListNode* curr = head;

        while (true)
        {
            bool enough_length = true;
            for (int i = 0; i < k; i++)
            {
                if (curr == NULL)
                {
                    enough_length = false;
                    break;
                }

                curr = curr->next;
            }

            if (enough_length == false)
                break;

            curr = prev->next;
            for (int i = 0; i < k - 1; i++)
            {
                ListNode* next = curr->next;

                curr->next = next->next;
                next->next = prev->next;
                prev->next = next;
            }

            prev = curr;
            curr = prev->next;
        }

        return dummyNode.next;
    }
};