// check if a linked list is circular or not
bool isCircular (node* head) {
  if (head == NULL) {
    return true;
  }
  node* temp = head -> next;
  while (temp != NULL && temp != head) {
    temp = temp -> next;
  }
  if (temp == head) {
    return true;
  }
  return false;
}

node* kReverse (node* head, int k) {
  // base case
  if (head == NULL) {
    return NULL;
  }

  // step 1: reverse first k nodes
  node* forward = NULL;
  node* curr = head;
  node* prev = NULL;
  int cnt = 0;
  while (curr != NULL && cnt < k) {
    forward = curr -> next;
    curr -> next = prev;
    prev = curr;
    curr = forward;
    cnt++;
    
  }
  // step 2: recursion
  if (forward != NULL) {
    head -> next = kReverse(forward, k);
    
  }
  // step 3: return head of the modified list
  return prev;
}

int getLength (node* head) {
  int length = 0;
  node* temp = head;
  while (temp != NULL) {
    length++;
    temp = temp -> next;
  }
  return length;
}

node* middleNode (node* head) {
  int length = getLength(head);
  int mid = (length/2) + 1;
  int cnt = 1;
  node* temp = head;
  while (cnt < mid) {
    temp = temp -> next;
    cnt++;
  }
  return temp;
}

node* reverseLinkedList (node* & head) {
  //empty list or single node
  if (head == NULL || head -> next == NULL) {
    return head;
  }
  node* prev = NULL;
  node* curr = head;
  node* forword = NULL;
  while (curr != NULL) {
    forword = curr -> next;
    curr -> next = prev;
    prev = curr;
    curr = forword;
  }
  return prev;
}

// it will return the head of the reversed linked list
node* reverse1 (node* head) {
  // base case
  if (head == NULL || head -> next == NULL) {
    return head;
  }
  node* chotaHead = reverse1(head -> next) {
    head -> next -> next = head;
    head -> next = NULL;

    return chotaHead;
  }
}

node* reverseLinkedList (node* head) {
  // empty  list 
	if (head == NULL || head -> next == NULL) {
	return head;
	}
  node* prev = NULL;
  node* curr = head;
  node* forword = NULL;
  
  while (curr != NULL) {
	forword = curr -> next;
    curr -> next = prev;
    prev = curr;
    curr = forword;
  }
  return prev;
}

void deleteNode (node* &head, node* &tail, int position) {
  // delete first node
  if (position == 1) {
    node* temp = head;
    temp -> next -> prev = NULL;
    head = temp -> next;
    temp -> next = NULL;
    delete temp;
    return;
  }
  node* curr = head;
  node* back = NULL;
  int cnt = 1;
  while (cnt < position) {
    back = curr;
    curr = curr -> next;
    cnt++;
  }
  //delete last node 
  if (curr -> next == NULL) {
    tail = back;
    back -> next = NULL;
    curr -> prev = NULL;
    delete curr;
    return;
  }
  // delete in between node 
  back -> next = curr -> next;
  curr -> next -> prev = back;
  curr -> next = NULL;
  curr -> prev = NULL;
  delete curr;
}

void insertAtPosition(node *&head, node *&tail, int position, int d) {
  // insert at start
  if (position == 1) {
    insertAtHead(head, tail, d);
    return;
  }
  node *temp = new node(d);
  node *curr = head;
  int cnt = 1;
  while (cnt < position - 1) {
    curr = curr->next;
    cnt++;
  }
  // insert at last
  if (curr->next == NULL) {
    insertAtTail(tail, head, d);
    return;
  } else {
    temp->next = curr->next;
    curr->next = temp;
    temp->prev = curr;
    curr->next->prev = temp;
  }
}

void insertAtTail(node *&tail, node* &head, int d) {
  node *temp = new node(d);
  if (tail == NULL) {
    tail = head = temp;
  } else {
    tail->next = temp;
    temp->prev = tail;
    tail = temp;
  }
}

void insertAtHead(node *&head, node* & tail, int d) {
  node *temp = new node(d);
  if (head == NULL) {
    head = tail = temp;
  } else {
    head->prev = temp;
    temp->next = head;
    head = temp;
  }
}

int getLen(node *head) {
  int len = 0;
  node *temp = head;
  while (temp != NULL) {
    len++;
    temp = temp->next;
  }
  return len;
}

class node {
public:
  int data;
  node *next;
  node *prev;
  node(int d) {
    this->data = d;
    this->next = NULL;
    this->prev = NULL;
  }
  ~node() {
    int value = this -> data;
    if (next != NULL) {
      delete next;
      next = NULL;
    }
    cout << "memory free for node with data " << value << endl;
  }
};

void insertInPosition(node *&head, node *&tail, int d, int position) {
  if (position == 1) {
    insertAtHead(head, d);
    return;
  }

  node *temp = head;
  int count = 1;
  while (count < position - 1) {
    temp = temp->next;
    count++;
  }
  if (temp->next == NULL) {
    insertAtTail(tail, d);
    return;
  }

  node *nodeToInsert = new node(d);
  nodeToInsert->next = temp->next;
  temp->next = nodeToInsert;
}

void print (node* &head) {
  node* temp = head;
  while (temp != NULL) {
    cout << temp -> data << " ";
    temp = temp -> next;
  }
}

void insertAtTail(node *&tail, int d) {
  node *temp = new node(d);
  tail->next = temp;
  tail = temp;
}

void insertAtHead(node *&head, int d) {
  node *temp = new node(d);
  temp->next = head;
  head = temp;
}

void deleteNode(node *&head, int position) {
  if (position == 1) {
    node *temp = head;
    head = head->next;
    temp->next = NULL;
    delete temp;
  }

  else {
    node *curr = head;
    node *prev = NULL;
    int cnt = 1;
    while (cnt < position) {
      prev = curr;
      curr = curr->next;
      cnt++;
    }
    prev->next = curr->next;
    curr->next = NULL;
    delete curr;
  }
}

void merge(int *arr, int s, int e) {
  int mid = s + (e - s) / 2;
  int len1 = mid - s + 1;
  int len2 = e - mid;
  int *first = new int[len1];
  int *second = new int[len2];

  // copy vales
  int mainArrayIndex = s;
  for (int i = 0; i < len1; i++) {
    first[i] = arr[mainArrayIndex++];
  }
  mainArrayIndex = mid + 1;
  for (int i = 0; i < len2; i++) {
    second[i] = arr[mainArrayIndex++];
  }

  // merge 2 sorted arrays
  int index1 = 0;
  int index2 = 0;
  mainArrayIndex = s;
  while (index1 < len1 && index2 < len2) {
    if (first[index1] < second[index2]) {
      arr[mainArrayIndex++] = first[index1++];
    } else {
      arr[mainArrayIndex++] = second[index2++];
    }
  }
  while (index1 < len1) {
    arr[mainArrayIndex++] = first[index1++];
  }
  while (index2 < len2) {
    arr[mainArrayIndex++] = second[index2++];
  }
}

void mergeSort(int *arr, int s, int e) {
  if (s >= e) {
    return;
  }
  int mid = s + (e - s) / 2;
  // left  part
  mergeSort(arr, s, mid);
  // right part
  mergeSort(arr, mid + 1, e);
  // merge
  merge(arr, s, e);
}

bool checkPalindrome (string s, int start, int length) {
  if (start>length) {
    return true;
	}
  if (s[start] != s[length]) {
    return false;
	}
  else {
    return checkPalindrome(s,start+1,length-1;)
  }
}

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

bool isSafe(int x, int y, int n, vector<vector<int>> visited,
            vector<vector<int>> &m) {
  if ((x >= 0 && x < n) && (y >= 0 && y < n) && visited[x][y] == 0 &&
      m[x][y] == 1) {
    return true;
  } else {
    return false;
  }
}

void solve(vector<vector<int>> &m, int n, vector<string> &ans, int x, int y,
           string path, vector<vector<int>> visited) {
  // you have reached x,y here

  // base case
  if (x == n - 1 && y == n - 1) {
    ans.push_back(path);
    return;
  }
  visited[x][y] = 1;

  // 4 choices D,L,R,U
  // down

  int newx = x + 1;
  int newy = y;
  if (isSafe(newx, newy, n, visited, m)) {
    path.push_back('D');
    solve(m, n, ans, newx, newy, path, visited);
    path.pop_back();
  }

  // left

  newx = x;
  newy = y - 1;
  if (isSafe(newx, newy, n, visited, m)) {
    path.push_back('L');
    solve(m, n, ans, newx, newy, path, visited);
    path.pop_back();
  }

  // right

  newx = x;
  newy = y + 1;
  if (isSafe(newx, newy, n, visited, m)) {
    path.push_back('R');
    solve(m, n, ans, newx, newy, path, visited);
    path.pop_back();
  }

  // up

  newx = x - 1;
  newy = y;
  if (isSafe(newx, newy, n, visited, m)) {
    path.push_back('U');
    solve(m, n, ans, newx, newy, path, visited);
    path.pop_back();
  }

  visited[x][y] = 0;
}

vector<string> findPath(vector<vector<int>> &m, int n) {
  vector<string> ans;
  if (m[0][0] == 0) {
    return ans;
  }
  int srcx = 0;
  int srcy = 0;

  vector<vector<int>> visited = m;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      visited[i][j] = 0;
    }
  }

  string path = "";
  solve(m, n, ans, srcx, srcy, path, visited);
  sort(ans.begin(), ans.end());
  return ans;
}

int main() {
  int n = 4;
  vector<vector<int>> m = {
      {1, 0, 0, 0}, {1, 1, 0, 1}, {1, 1, 0, 0}, {0, 1, 1, 1}};
  vector<string> ans = findPath(m, n);
  for (int i = 0; i < ans.size(); i++) {
    cout << ans[i] << " ";
  }
  cout << endl;
  return 0;
}

void sortArray (int *arr, int n) {
  if (n==0||n==1)
    return;
  for (int i=0; i<n-1; i++) {
    if (arr[i]>arr[i+1]) {
      swap(arr[i],arr[i+1]);
    }
  }
  sortArray(arr,n-1);
}

int power (int a, int b) {
  if (b==0)
    return 1;
  if (b==1)
    return a;
  int ans = power(a,b/2);
  if (b%2==0)
    return ans*ans;
  else
    return a*ans*ans;
}

bool binarySearch(int arr[], int s, int e, int key) {
  if (s > e)
    return false;
  int mid = s + (e - s) / 2;
  if (arr[mid] == key)
    return true;
  if (arr[mid] < key)
    return binarySearch(arr, mid + 1, e, key);
  else
    return binarySearch(arr, s, mid - 1, key);
}

bool linearsearch (int *arr, int size, int key) {
  if (size == 0)
    return false;
  if(arr[0]==key)
    return true;
  else 
    return linearsearch(arr+1, size-1, key);
}

bool isArraySorted (int arr[],int size) {
  if (size == 0 || size == 1) 
    return true;
  if (arr[0]>arr[1]) 
    return false;
  else {
    bool remainingPart = isArraySorted(arr+1,size-1); 
    return remainingPart;
  }
  
}

class Solution {
public:
    int fib(int n) {
        if (n==0)
        return 0;
        if (n==1)
        return 1;
        return fib(n-1)+fib(n-2);
        
    }
};

#include <iostream>
using namespace std;

void sayDigit (int n,string arr[]) {
  if (n==0) 
    return;
  if (n>0) {
    int digit = n%10;
    n = n/10;
    sayDigit(n,arr);
    cout << arr[digit] << " ";
  }
}

int main () {
  string arr[10] = {"zero","one","two","three","four","five","six","seven","eight","nine"};
  int n;
  cin >> n;
  sayDigit(n,arr);
  return 0;
}

vector<int> spiralPrint(vector<vector<int>> v, int r, int c) {
  vector<int> ans;
  int count = 0;
  ;
  int total = r * c;
  int startingRow = 0;
  int endingRow = r - 1;
  int startingCol = 0;
  int endingCol = c - 1;

  while (count < total) {
    // print starting row
    for (int i = startingCol; i <= endingCol && count < total; i++) {
      ans.push_back(v[startingRow][i]);
      count++;
    }
    startingRow++;
    // printing ending col
    for (int i = startingRow; i <= endingRow && count < total; i++) {
      ans.push_back(v[i][endingCol]);
      count++;
    }
    endingCol--;
    // printing ending row
    for (int i = endingCol; i >= startingCol && count < total; i--) {
      ans.push_back(v[endingRow][i]);
      count++;
    }
    endingRow--;
    // printing starting col
    for (int i = endingRow; i >= startingRow && count < total; i--) {
      ans.push_back(v[i][startingCol]);
      count++;
    }
    startingCol++;
  }

  return ans;
}

vector<int> wavePrint(vector<vector<int>> arr, int r, int c) {
  vector<int> ans;
  for (int col = 0; col < c; col++) {
    if (col & 1) {
      // odd index -> bottom to top
      for (int row = r - 1; row >= 0; row--) {
        cout << arr[row][col] << " ";
        ans.push_back(arr[row][col]);
      }
    }
    // 0 or even index -> top to bottom
    else {
      for (int row = 0; row < r; row++) {
        cout << arr[row][col] << " ";
        ans.push_back(arr[row][col]);
      }
    }
  }

  return ans;
}

#include <iostream>
#include <string>
using namespace std;

string addInplaceOfSpaces (string &s) {
  string temp = "";
  for (int i = 0; i < s.length(); i ++) {
    if (s[i] == ' ') {
      temp.push_back('@');
      temp.push_back('2');
      temp.push_back('3');
    }
    else {
      temp.push_back(s[i]);
    }
  }
  return temp;
}

int main() {
  string s ="my name is vishnu deb jha" ;
  string v = addInplaceOfSpaces(s);
  cout << v << endl;
  return 0;
}
// output is my@23name@23is@23vishnu@23deb@23jha

char getMaxOccCharacter(string s) {
  int arr[26] = {0};
  for (int i = 0; i < s.length(); i++) {
    char ch = s[i];
    int number = 0;
    number = ch - 'a';
    arr[number]++;
  }
  int maxi = -1, ans = 0;
  for (int i = 0; i < 26; i++) {
    if (arr[i] > maxi) {
      maxi = arr[i];
      ans = i;
    }
  }
  return 'a' + ans;
}

void mergeArray(int arr1[], int n, int arr2[], int m, int arr3[]) {
  int i, j, k;
  i = j = k = 0;
  while (i < n && j < m) {
    if (arr1[i] < arr2[j]) {
      arr3[k] = arr1[i];
      k++;
      i++;
    } else {
      arr3[k] = arr2[j];
      k++;
      j++;
    }
  }
  while (i < n) {
    arr3[k] = arr1[i];
    i++;
    k++;
  }
  while (j < m) {
    arr3[k] = arr2[j];
    k++;
    j++;
  }
}

void reverseArray (int arr[],int n) {
  int start = 0;
  int end = n-1;
  while (start<=end) {
    swap (arr[start],arr[end]);
      start++;
    end--;
  }
}

void sortArray(int arr[], int n) {
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < (n - i); j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr[j], arr[j + 1]);
      }
    }
  }
}

#include <iostream>
using namespace std;

void printArray (int arr[],int n) {
  for (int i= 0; i< n; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}

void sortArray (int arr[], int n) {
  for (int i = 0; i < (n-1); i ++) {
    for (int j = (i+1); j < n; j++) {
      if (arr[i] > arr[j]) {
        swap (arr[i], arr[j]);
      }
    }
  }
}

int main () {
  int n;
  cout << "Enter the size of the array: " << endl;
  cin >> n;
  int arr[n];
  cout << "Enter the elements of the array: " << endl;
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  cout << "The array before sorting: " << endl;
  printArray (arr, n);
  sortArray (arr, n);
  cout << "the array after sorting :" << endl;
  printArray(arr,n);
  return 0;
}

#include <iostream>
using namespace std;

bool allocationIsPossible(int arr[], int n, int m, int mid) {
    int sum = 0;
    int studentCount = 1;
    for (int i = 0; i < n; i++) {
        if (sum + arr[i] <= mid) {
            sum += arr[i];
        } else {
            studentCount++;
            if (studentCount > m || arr[i] > mid) {
                return false;
            }
            sum = arr[i];
        }
    }
    return true;
}

int bookAllocate(int arr[], int n, int m) {
    int start = 0;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    int end = sum;
    int mid = start + (end - start) / 2;
    int ans = -1;
    while (start <= end) {
        if (allocationIsPossible(arr, n, m, mid)) {
            ans = mid;
            end = mid - 1;
        } else {
            start = mid + 1;
        }
        mid = start + (end - start) / 2;
    }
    return ans;
}

int main() {
    int arr[4] = {10, 20, 30, 40};
    int ans = bookAllocate(arr, 4, 2);
    cout << "Minimum pages: " << ans << endl;
    return 0;
}
  

// output is 60

#include <iostream>
using namespace std;

bool allocationIsPossible(int arr[], int n, int m, int mid) {
    int sum = 0;
    int studentCount = 1;
    for (int i = 0; i < n; i++) {
        if (sum + arr[i] <= mid) {
            sum += arr[i];
        } else {
            studentCount++;
            if (studentCount > m || arr[i] > mid) {
                return false;
            }
            sum = arr[i];
        }
    }
    return true;
}

int bookAllocate(int arr[], int n, int m) {
    int start = 0;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum += arr[i];
    }
    int end = sum;
    int mid = start + (end - start) / 2;
    int ans = -1;
    while (start <= end) {
        if (allocationIsPossible(arr, n, m, mid)) {
            ans = mid;
            end = mid - 1;
        } else {
            start = mid + 1;
        }
        mid = start + (end - start) / 2;
    }
    return ans;
}

int main() {
    int arr[4] = {10, 20, 30, 40};
    int ans = bookAllocate(arr, 4, 2);
    cout << "Minimum pages: " << ans << endl;
    return 0;
}
  

// output is 60

#include <iostream>
using namespace std;
int sqrt(int arr[], int n, int key) {
  int start = 0;
  int end = n - 1;
  int mid = start + (end - start) / 2;
  int ans = -1;
  while (start <= end) {
    int square = mid * mid;
    if (square == key) {
      return mid;
    } else if (square > key) {
      end = mid - 1;
    } else {
      start = mid + 1;
      ans = mid;
    }
    mid = start + (end - start) / 2;
  }
  return ans;
}
double precision(int n, int precision, int integer) {
  double factor = 1;
  double ans = integer;
  for (int i = 0; i < precision; i++) {
    factor = factor / 10;
    for (double j = ans; j * j < n; j += factor) {
      ans = j;
    }
  }
  return ans;
}
int main() {
  int n;
  cout << "enter the number :" << endl;
  cin >> n;
  int arr[n];
  for (int i = 0; i < n; i++) {
    arr[i] = (i + 1);
  }
  int squareRoot = sqrt(arr, n, n);
  double finalAns = precision(n, 3, squareRoot);
  cout << "square root of " << n << " is " << finalAns << endl;
  return 0;
}

#include <iostream>
using namespace std;
long long int binarySearch(int arr[],int n,int key) {
  int start = 0;
  int end = n-1;
  long long int mid = start + (end-start)/2;
  long long int ans = -1;
while (start <= end){
  long long int square = mid*mid;
  if (square == key) {
    return mid;
  }
  else if (square > key) {
    end = mid - 1;
  }
  else {
    start = mid + 1;
    ans = mid;
  }
  mid = start + (end-start)/2;
}
  return ans;
}
int main() {
  int n;
  cout << "enter the number :" << endl;
  cin >> n;
  int arr[n];
  for (int i = 0; i < n; i++) {
     arr[i] = (i+1);
  }
  int squareRoot = binarySearch(arr,n,n);
  cout << "square root of " << n << " is " << squareRoot << endl;
  return 0;
}

#include <iostream>
using namespace std;
int pivotSearch (int arr[],int n) {
  int start = 0;
  int end = n-1;
  int mid = start + (end-start)/2;
  while (start < end) {
    if (arr[mid] >= arr[0]) {
      start = mid + 1;
    }
    else {
      end = mid;
    }
    mid = start + (end-start)/2;
  }
  return end;
}
int binarySearch(int arr[],int n,int s,int e,int key) {
  int start = s;
  int end = e;
  int mid = start + (end-start)/2;
while (start <= end){
  if (arr[mid] == key) {
    return mid;
  }
  else if (arr[mid] > key) {
    end = mid - 1;
  }
  else {
    start = mid + 1;
  }
  mid = start + (end-start)/2;
}
  return -1;
}
int main() {
  int arr[6] = {3,8,10,0,1,2};
  int ans = pivotSearch(arr,6);
  cout << "the pivot is at : "<< ans << endl;
  if (2>=arr[ans]&&2<=arr[5]) {
    cout << "the element is present in the array at index     :" << binarySearch(arr,6,ans,5,2); 
  }
  else {
    cout << "the element is present in the array at index     :" << binarySearch(arr,6,0,ans-1,2);
  }
  return 0;
}

#include <iostream>
using namespace std;
int pivotSearch (int arr[],int n) {
  int start = 0;
  int end = n-1;
  int mid = start + (end-start)/2;
  while (start < end) {
    if (arr[mid] >= arr[0]) {
      start = mid + 1;
    }
    else {
      end = mid;
    }
    mid = start + (end-start)/2;
  }
  return end;
}
int main() {
  int arr[5] = {3,8,10,17,1};
  int ans = pivotSearch(arr,5);
  cout << "the pivot is : "<< ans;
  return 0;
}

// c++ program to create a linked list insert element at head, at tail and delete element from
// tail, head and specific key
#include <iostream>
using namespace std;
struct Node
{
public:
    int data;
    Node *next;
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};
void insertAtHead(Node *&head, int data)
{
    Node *NewNode = new Node(data);
    NewNode->next = head;
    head = NewNode;
}
void insertAtTail(Node *&head, int data)
{
    Node *NewNode = new Node(data);
    if (head == NULL)
    {
        NewNode->next = head;
        head = NewNode;
        return;
    }
    Node *temp = head;
    while (temp->next != NULL)
    {
        temp = temp->next;
    }
    temp->next = NewNode;

    cout << "the value of temp next is " << temp->data << endl;
}
void insertAtKey(Node *&head, int key, int data)
{
    Node *NewNode = new Node(data);
    if (head->data == key)
    {

        NewNode->next = head->next;
        head->next = NewNode;
        return;
    }
    Node *temp = head;
    while (temp->data != key)
    {
        temp = temp->next;
        if (temp == NULL)
            return;
    }
    NewNode->next = temp->next;
    temp->next = NewNode;
}
void print(Node *&head)
{
    if (head == NULL)
    {
        cout << head->data << " ->  ";
    }
    Node *temp = head;
    while (temp != NULL)
    {
        /* code */
        cout << temp->data << " -> ";
        temp = temp->next;
    }
}

void deleteNode(Node *&head, int key)
{
    if (head == NULL)
        return;

    if (head->data == key)
    {
        Node *temp = head;
        head = head->next;
        delete temp;
    }
    deleteNode(head->next, key);
}
// recursive approach to reverse the linked list
Node *Reverse(Node *&head)
{
    if (head == NULL || head->next == NULL)
        return head;
    Node *NewHead = Reverse(head->next);
    head->next->next = head;
    head->next = NULL;
    return NewHead;
}
//this function reverse the k nodes in linked list
Node*Reversek(Node*&head,int k){
//first we have to make three node pointers

Node *prevPtr = NULL;//the prev ptr points to Null
Node *currPtr = head;//the next ptr should points toward the prev ptr because we have to reverse 
//the nodes this is possible if we point the next node towards the prev node
Node *nextptr=NULL;//we will assign the value to nextptr in the loop 
int count = 0;
while(currPtr!=NULL && count<k)
{
    nextptr = currPtr->next;
    currPtr->next = prevPtr;
    prevPtr = currPtr;
    currPtr = nextptr;
    count++;
}
if(nextptr!=NULL){
head->next = Reversek(nextptr, k);
}
return prevPtr;
}
int main()
{
    Node *head = NULL;
    cout << "insert At head" << endl;
    insertAtHead(head, 3);
    insertAtHead(head, 2);
    print(head);
    cout << endl;
    cout << "Insert at Tail " << endl;
    insertAtTail(head, 4);
    insertAtTail(head, 5);
    insertAtTail(head, 6);
    insertAtTail(head, 10);
    insertAtTail(head, 9);
    insertAtKey(head, 10, 45);
    print(head);

    deleteNode(head, 2);
    cout << "deleting the head" << endl;
    print(head);
    cout << endl;
    cout << "reversing the linked list " << endl;
    Node *NewHead = Reverse(head);
    print(NewHead);
    cout << endl;
    cout << "reversing the k nodes in linked list " << endl;
    Node *NewRev = Reversek(NewHead,2);
    print(NewRev);
}

Node*Reversek(Node*&head,int k){
//first we have to make three node pointers

Node *prevPtr = NULL;//the prev ptr points to Null
Node *currPtr = head;//the next ptr should points toward the prev ptr because we have to reverse 
//the nodes this is possible if we point the next node towards the prev node
Node *nextptr=NULL;//we will assign the value to nextptr in the loop 
int count = 0;
while(currPtr!=NULL && count<k)
{
    nextptr = currPtr->next;
    currPtr->next = prevPtr;
    prevPtr = currPtr;
    currPtr = nextptr;
    count++;
}
if(nextptr!=NULL){
head->next = Reversek(nextptr, k);
}
return prevPtr;
}

// c++ program to create a linked list insert element at head, at tail and delete element from
// tail, head and specific key
#include <iostream>
using namespace std;
struct Node
{
public:
    int data;
    Node *next;
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};
void insertAtHead(Node *&head, int data)
{
    Node *NewNode = new Node(data);
    NewNode->next = head;
    head = NewNode;
}
void insertAtTail(Node *&head, int data)
{
    Node *NewNode = new Node(data);
    if (head == NULL)
    {
        NewNode->next = head;
        head = NewNode;
        return;
    }
    Node *temp = head;
    while (temp->next != NULL)
    {
        temp = temp->next;
    }
    temp->next = NewNode;

    cout << "the value of temp next is " << temp->data << endl;
}
void insertAtKey(Node *&head, int key, int data)
{
    Node *NewNode = new Node(data);
    if (head->data == key)
    {

        NewNode->next = head->next;
        head->next = NewNode;
        return;
    }
    Node *temp = head;
    while (temp->data != key)
    {
        temp = temp->next;
        if (temp == NULL)
            return;
    }
    NewNode->next = temp->next;
    temp->next = NewNode;
}
void print(Node *&head)
{
    if (head == NULL)
    {
        cout << head->data << " ->  ";
    }
    Node *temp = head;
    while (temp != NULL)
    {
        /* code */
        cout << temp->data << " -> ";
        temp = temp->next;
    }
}

void deleteNode(Node *&head, int key)
{
    if (head == NULL)
        return;

    if (head->data == key)
    {
        Node *temp = head;
        head = head->next;
        delete temp;
    }
    deleteNode(head->next, key);
}
// recursive approach to reverse the linked list
Node *Reverse(Node *&head)
{
    if (head == NULL || head->next == NULL)
        return head;
    Node *NewHead = Reverse(head->next);
    head->next->next = head;
    head->next = NULL;
    return NewHead;
}
int main()
{
    Node *head = NULL;
    cout << "insert At head" << endl;
    insertAtHead(head, 3);
    insertAtHead(head, 2);
    print(head);
    cout << endl;
    cout << "Insert at Tail " << endl;
    insertAtTail(head, 4);
    insertAtTail(head, 5);
    insertAtTail(head, 6);
    insertAtTail(head, 10);
    insertAtTail(head, 9);
    insertAtKey(head, 10, 45);
    print(head);

    deleteNode(head, 2);
    cout << "deleting the head" << endl;
    print(head);
    cout << endl;
    cout << "reversing the linked list " << endl;
    Node *NewHead = Reverse(head);

    print(NewHead);
}

Node *Reverse(Node *&head)
{
    if (head == NULL || head->next == NULL)
        return head;
    Node *NewHead = Reverse(head->next);
    head->next->next = head;
    head->next = NULL;
    return NewHead;
}
//in main the previous head becomes the last node
int main(){
  Node*newHead=Reverse(head);
  print(newhead);
}

// c++ program to create a linked list insert element at head, at tail and delete element from
// tail, head and specific key
#include <iostream>
using namespace std;
struct Node
{
public:
    int data;
    Node *next;
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};
void insertAtHead(Node *&head, int data)
{
    Node *NewNode = new Node(data);
    NewNode->next = head;
    head = NewNode;
}
void insertAtTail(Node *&head, int data)
{
    Node *NewNode = new Node(data);
    if (head == NULL)
    {
        NewNode->next = head;
        head = NewNode;
        return;
    }
    Node *temp = head;
    while (temp->next != NULL)
    {
        temp = temp->next;
    }
    temp->next = NewNode;

    cout << "the value of temp next is " << temp->data << endl;
}
void insertAtKey(Node *&head, int key, int data)
{
    Node *NewNode = new Node(data);
    if (head->data == key)
    {

        NewNode->next = head->next;
        head->next = NewNode;
        return;
    }
    Node *temp = head;
    while (temp->data != key)
    {
        temp = temp->next;
        if (temp == NULL)
            return;
    }
    NewNode->next = temp->next;
    temp->next = NewNode;
}
void print(Node *&head)
{
    if (head == NULL)
    {
        cout << head->data << " ->  ";
    }
    Node *temp = head;
    while (temp != NULL)
    {
        /* code */
        cout << temp->data << " -> ";
        temp = temp->next;
    }
}

void deleteNode(Node *&head, int key)
{
    if (head == NULL)
        return;

    if (head->data == key)
    {
        Node *temp = head;
        head = head->next;
        delete temp;
    }
    deleteNode(head->next, key);
}
int main()
{
    Node *head = NULL;
    cout << "insert At head" << endl;
    insertAtHead(head, 3);
    insertAtHead(head, 2);
    print(head);
    cout << endl;
    cout << "Insert at Tail " << endl;
    insertAtTail(head, 4);
    insertAtTail(head, 5);
    insertAtTail(head, 6);
    insertAtTail(head, 10);
    insertAtTail(head, 9);
    insertAtKey(head, 10, 45);
    print(head);

    deleteNode(head, 2);
    cout << "deleting the head" << endl;
    print(head);
}

#include<iostream>
using namespace std;
struct Node {
public:
	int data;
	Node* next;
	Node(int data=0)
	{
		this->data = data;
		this->next = NULL;
	}
};
void push(Node** head_ref, int data) {
	//creating the new node and by using constructor we 
	//are storing the value of the data
	//firstly the next pointer of this new node points to NULL
	//as declared in the constructor
	//then we are pointing the pointer of this node to the new node
	//and lastly we are equating the new insert node to the previous 
	//node to connect it to the list
	Node* new_node = new Node(data);
	new_node->next =(* head_ref);
	*(head_ref) = new_node;

}
void print(Node*& head) {

	Node* temp =  head;
	while (temp != NULL)
	{
		cout << "the value of the data is " << temp->data << endl;
		temp = temp->next;
	}

}

int main() {
	Node* node;
	node = NULL;
	push(&node, 5);
	push(&node, 6);
	push(&node, 7);
	print(node);
	return 0;


}

#include<iostream>
using namespace std;
void sort(int* array, int size) {
	int key = 0, j = 0;
	for (int i = 1; i < size; i++)
	{
		key = array[i];
		j = i - 1;
		while (j >= 0 && array[j] > key)
		{
			array[j + 1] = array[j];
			j = j - 1;
		}
		array[j + 1] = key;
	}
	for (int i = 0; i < size; i++)
		cout << array[i] << "  ";
}
int main() {
	int size = 0;
	cout << "Enter size of the array " << endl;
	cin >> size;
	int* array = new int[size];
	cout << "Enter elements of the array " << endl;
	for (int i = 0; i < size; i++)
		cin >> array[i];
	sort(array, size);
}

What you will learn :

 - All important concepts of Data Structures & Algorithms

 - How to enhance your problem solving skills for the product-based companies

 - Extensive knowledge on algorithms & frequently asked questions to help better your coding skills

 - Learn the problem-solving approach for the puzzle based questions asked in interviews