CODEWITHSUNDEEP
c++data-structureslinked-listtime-complexityspace-complexity
Rocket
Rocket

Reputation: 123

What is the space complexity of my code? (Linked List)

I was solving a problem related to linked lists I wrote some code which works perfectly fine but I am not able to analyse the space complexity of my code. This is the problem, You have been given a singly linked list of integers along with two integers, 'M,' and 'N.' Traverse the linked list such that you retain the 'M' nodes, then delete the next 'N' nodes. Continue the same until the end of the linked list.

I wrote this code to solve this problem.

Node *skipMdeleteN(Node *head, int M, int N) {
  if (head == NULL) return head;
  if (M == 0) return NULL;
  if (N == 0) return head;
  Node *current = head;
  Node *dummy1 = new Node(-1);
  Node *dummy2 = new Node(-1);
  Node *FinalHead;
  Node *dummy2Head;
  Node *prev;
  int i = 0;
  int j = 0;
  int Head = 0;
  while (current != NULL) {
    if (i <= M - 1) {
      dummy1->next = current;
      dummy1 = dummy1->next;
      if (Head == 0) {
        FinalHead = dummy1;
        Head++;
      }
    }
    if (i >= M && i <= ((M + N) - 1)) {
      dummy2->next = current;
      dummy2 = dummy2->next;
      if (j == 0) {
        dummy2Head = dummy2;
        j++;
      }
    }
    if (i == ((M + N) - 1)) {
      i = 0;
    } else {
      i++;
    }
    current = current->next;
  }
  dummy1->next = NULL;
  dummy2->next = NULL;
  dummy1 = dummy1->next;
  dummy2 = dummy2->next;
  while (dummy2Head != NULL) {
    prev = dummy2Head;
    dummy2Head = dummy2Head->next;
    delete (prev);
  }
  return FinalHead;
}

This code works perfectly fine and the logic behind the code is following:

I create 2 dummy nodes(dummy1 and dummy2) and then I start traversing the linked list, for the first M nodes I keep on attaching those nodes at the end of dummy1 node. Once M nodes are done then I start attaching the next N nodes at the end of dummy2 node which I will delete in the end. So this attaches all the M nodes which I want to retain at the end of the dummy1 list, whose head I return.

The time complexity of my code is O(N) because I am traversing the list. I am not sure what the space complexity will be, will using 2 dummy nodes make it a linear space complexity because they are acting like a linked list. Please explain!

Upvotes: 1

Views: 951

Answers (1)

Aivean
Aivean

Reputation: 10882

There are two space complexity metrics: total space complexity and auxiliary (extra) space complexity.

Total includes input, while auxiliary doesn't.

In your case, input size is O(n) and you're modifying it, using O(1) extra space. After modifications, input is still O(n). Here n denotes the size of the list.

Which translates to O(n) total space complexity and O(1) auxiliary space complexity.

Upvotes: 1

Related Questions