thiscodeWorks - Organizing the best of code online

##c++ ##dsa ##linkedlist ##circular ##loop #floyd'sloopdetection ##algorithm #mergesort

node *findMid(node *head) {
  node *slow = head;
  node *fast = head->next;
  while (fast != NULL && fast->next != NULL) {
    slow = slow->next;
    fast = fast->next->next;
  }
  return slow;
}

node *merge(node *left, node *right) {
  if (left == NULL) {
    return right;
  }
  if (right == NULL) {
    return left;
  }
  node *ans = new node(-1);
  node *temp = ans;
  while (left != NULL && right != NULL) {
    if (left->data < right->data) {
      temp->next = left;
      temp = left;
      left = left->next;
    } else {
      temp->next = right;
      temp = right;
      right = right->next;
    }
  }
  while (left != NULL) {
    temp->next = left;
    temp = left;
    left = left->next;
  }
  while (right != NULL) {
    temp->next = right;
    temp = right;
    right = right->next;
  }
  ans = ans->next;
  return ans;
}

node *mergeSort(node *head) {
  // base case
  if (head == NULL || head->next == NULL) {
    return head;
  }
  // breaking the linked list into two halves
  node *mid = findMid(head);
  node *first = head;
  node *second = mid->next;
  mid->next = NULL;
  // recursive call
  first = mergeSort(first);
  second = mergeSort(second);
  // merging the two sorted halves
  node *result = merge(first, second);
  return result;
}

##c++ ##dsa ##linkedlist ##circular ##loop #floyd'sloopdetection ##algorithm

sort 0, 1, 2 in linked list

node* sortList (node* head) {
  int zeroCount = 0;
  int oneCount = 0;
  int twoCount = 0;
  node* temp = head;
  while (temp != NULL) {
    if (temp -> data == 0) {
      zeroCount++;
    }
    else if (temp -> data == 0) {
      oneCount++;
    }
    else if (temp -> data == 0) {
      twoCount++;
    }
    temp = temp -> next;
  }
  temp = head;
  while (temp != NULL) {
    if (zeroCount != 0) {
      temp -> data = 0;
      zeroCount--;
    }
    else if (oneCount != 0) {
      temp -> data = 1;
      oneCount--;
    }
    else if (twoCount != 0) {
      temp -> data = 2;
      twoCount--;
    }
    temp = temp -> next;
  }
  return temp;
}

##c++ ##dsa ##linkedlist ##circular ##loop #floyd'sloopdetection ##algorithm

remove loop from linked list

void removeLoop(node *head) {
  if (head == NULL) {
    return;
  }
  node *startOfLoop = getStartingNode(head);
  node *temp = startOfLoop;
  while (temp->next != startOfLoop) {
    temp = temp->next;
  }
  temp->next = NULL;
  cout << "loop is removed " << endl;
}

##c++ ##dsa ##linkedlist ##circular ##loop #floyd'sloopdetection ##algorithm

starting node of a loop in linked list

node *floyedDetectionLoop(node *head) {
  if (head == NULL) {
    return NULL;
  }
  node *fast = head;
  node *slow = head;
  while (fast != NULL && slow != NULL) {
    fast = fast->next;
    if (fast->next != NULL) {
      fast = fast->next;
    }
    slow = slow->next;
    if (fast == slow) {
      return slow;
    }
  }
  return NULL;
}

node *getStartingNode(node *head) {
  if (head == NULL) {
    return NULL;
  }
  node *intersection = floyedDetectionLoop(head);
  node *slow = head;
  while (slow != intersection) {
    slow = slow->next;
    intersection = intersection->next;
  }
  return slow;
}

##c++ ##dsa ##linkedlist ##circular ##loop #floyd'sloopdetection ##algorithm

floyd's loops detection algorithm

bool floyedDetectionLoop (node* head) {
  if (head == NULL) {
    return false;
  }
  node* fast = head;
  node* slow = head;
  while (fast != NULL && slow != NULL) {
    fast = fast -> next;
    if (fast -> next == NULL) {
      fast = fast -> next;
    }
    slow = slow -> next;
    if (fast == slow) {
      return true;
    }
    
  }
  return false;
}

merge sort of linked list

sort 0, 1, 2 in linked list

remove loop from linked list

starting node of a loop in linked list

floyd's loops detection algorithm

Save snippets that work with our extensions