Max element in current element. Implementation using the concept of doubly ended queued but with simple arrays and two pointers.

0
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <queue>

using namespace std;

/*Let the Current window size be K.
10 Elements and 4 is size of the window
Input : 10 3
1 5 2 6 4 8 6 2 3 5

Output: 5 6 6 8 8 8 6 5
*/

int a[1000];
int q[1000];
vector<int> ans;
int main()
{ //Front of queue is the side where we enter new element.
//back is the side from which we remove old element.
//Here basically a doubly ended queue is implemented using
//simple array and two pointers pointing to the back and
//front respectively. :-)
int n, k;
int front1 = -1, back1 = 0;
cin >> n >> k;
for(int i = 0; i < n; i++)
cin >> a[i];
for(int i = 0; i < n; i++){

while(front1 >= back1 && q[front1] < a[i]) //While atleast 1 element is present and
//current element is greater then front
//of queue, remove from front.
front1--;
q[++front1] = a[i]; //Add new element to front.

if(i >= k && q[back1] == a[i-k]) //If current element is equal to element
//at the back, remove front the back.
back1++;
if(i >= k -1) //Print after iterating k-1 times
cout << q[back1] << endl;
// for(int j = back1; j <= front1; j++) //Can be used to print current status of queue
// cout << q[j] << " " ;
// cout << endl;
}

}

Swap the nth and the mth node in a linked list

0

In this case n = 2 and m = 4.
Please give a linked list of size > 4. Corner cases are not handled. Only the main swapping part is handled.

 

#include <iostream>
#include <algorithm>
#include <cstdlib>

using namespace std;

typedef struct node{
int data;
node *next;
};

node *allocate(){
node *ptr = (node *)malloc(sizeof(node));
ptr -> next = NULL;
return ptr;
}

node *f(){
int x;
cin >> x;
if(x == -1)
return NULL;
node *head = allocate();
head ->data = x;
head ->next = f();
return head;
}

int main()
{
cout << "Enter items of list:-\nType -1 to exit.\n";
node *head;
head = NULL;
head = f();
node *temp = head;
while(temp!= NULL)
cout << temp->data << " ", temp = temp->next;
node *ptr2, *ptr4;
temp = head;
for(int i = 0; i < 4; i++){
if(i == 0)
ptr2 = temp;
else if(i == 2)
ptr4 = temp;
temp = temp -> next;
}

// cout << ptr2->data << " " << ptr4->data << endl;
temp = (ptr2->next) -> next;
ptr2->next->next = ptr4->next->next;
ptr4->next->next = temp;

temp = ptr2->next;
ptr2->next = ptr4->next;
ptr4->next = temp;
cout << endl;
temp = head;
// system ("pause");
while(temp!= NULL)
cout << temp->data << " ", temp = temp->next;

return 0;
}

Reverse every K nodes in a linked list.

0

In this example k = 4 (initialized at the beginning of main function. Change according to needs.)

original list – 1 2 3 4 5 6 7 8 9 10

final list – 4 3 2 1 8 7 6 5 10 9


#include <iostream>
#include <algorithm>
#include <cstdlib>

using namespace std;

typedef struct node{
int data;
node *next;
};

node *allocate(){
node *ptr = (node *)malloc(sizeof(node));
ptr -> next = NULL;
return ptr;
}

node *f(){
int x;
cin >> x;
if(x == -1)
return NULL;
node *head = allocate();
head ->data = x;
head ->next = f();
return head;
}

node *rev(node *head){
if(head == NULL || head->next == NULL)
return head;
node *A = head;
node *B = head -> next;
node *C = head;
A->next = B->next;
A = B;
B -> next = C;
head = B;
head -> next -> next = rev(head ->next ->next);
return B;
}

int main()
{
cout << "Enter items of list:-\nType -1 to exit.\n";
node *head;
head = NULL;
head = f();
node *temp = head;
cout << "The original list is\n";
while(temp!= NULL)
cout << temp->data << " ", temp = temp->next;
head = rev(head);
cout << endl;
temp = head;
cout << "The pairwise reversed list is\n";
while(temp!= NULL)
cout << temp->data << " ", temp = temp->next;
return 0;
}



Reverse a linked list in pairs

0

#include <iostream>
#include <algorithm>
#include <cstdlib>

using namespace std;

typedef struct node{
int data;
node *next;
};

node *allocate(){
node *ptr = (node *)malloc(sizeof(node));
ptr -> next = NULL;
return ptr;
}

node *f(){
int x;
cin >> x;
if(x == -1)
return NULL;
node *head = allocate();
head ->data = x;
head ->next = f();
return head;
}

node *rev(node *head){
if(head == NULL || head->next == NULL)
return head;
node *A = head;
node *B = head -> next;
node *C = head;
A->next = B->next;
A = B;
B -> next = C;
head = B;
head -> next -> next = rev(head ->next ->next);
return B;
}

int main()
{
cout << "Enter items of list:-\nType -1 to exit.\n";
node *head;
head = NULL;
head = f();
node *temp = head;
cout << "The original list is\n";
while(temp!= NULL)
cout << temp->data << " ", temp = temp->next;
head = rev(head);
cout << endl;
temp = head;
cout << "The pairwise reversed list is\n";
while(temp!= NULL)
cout << temp->data << " ", temp = temp->next;
return 0;
}

Reverse a linked list

0

#include <iostream>
#include <algorithm>
#include <cstdlib>

using namespace std;

typedef struct node{
int data;
node *next;
};

node *allocate(){
node *ptr = (node *)malloc(sizeof(node));
ptr -> next = NULL;
return ptr;
}

node *f(){
int x;
cin >> x;
if(x == -1)
return NULL;
node *head = allocate();
head ->data = x;
head ->next = f();
return head;
}

node *rev(node **curr, node *last){
if((*curr)->next == NULL){
(*curr)->next = last;
return (*curr);
}
node *temp = rev(&((*curr)->next), *curr);
if(last != NULL)
(*curr)->next = last;
else
(*curr)->next = NULL;
return temp;
}

int main()
{
cout << "Enter items of list:-\nType -1 to exit.\n";
node *head;
head = NULL;
head = f();
node *temp = head;
cout << "old list is \n";
while(temp!= NULL)
cout << temp->data << " ", temp = temp->next;
head = rev(&head, NULL);
cout << endl;
temp = head;
cout << "New list is \n";
while(temp!= NULL)
cout << temp->data << " ", temp = temp->next;
return 0;
}

Linked list Implementation with a return type of node*

0

#include <iostream>
#include <algorithm>
#include <cstdlib>

using namespace std;

typedef struct node{
int data;
node *next;
};

node *allocate(){
node *ptr = (node *)malloc(sizeof(node));
ptr -> next = NULL;
return ptr;
}

node *f(){
int x;
cin >> x;
if(x == -1)
return NULL;
node *head = allocate();
head ->data = x;
head ->next = f(); //Point the next pointer to the next node
//whose address is returned recursively.
return head; //return the pointer to the current node
}

int main()
{
cout << "Enter items of list:-\nType -1 to exit.\n";
node *head;
head = NULL;
head = f();
while(head!= NULL)
cout << head->data << " ", head = head->next;
return 0;
}

A simple linked list implementation with no¬†return type and no global pointers.

0

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <utility>

using namespace std;

typedef struct node{
int data;
node *next;
};

node * alloc(){ //allocate and return the new allocated memory of type node
node *ptr = (node*)malloc(sizeof(node));
ptr -> next = NULL;
ptr -> data = 0;
}

void f(node **head){
int x;
cin >> x;
if(x == -1) //no more data
return ;
*head = alloc(); //allocate new memory
(*head)->data = x;
f(&((*head)->next)); //pass the next pointer of current node to be used recursively.
}

int main()
{
cout << "Enter items of list:-\nType -1 to finish.\n";
node *head = NULL;
f(&head);
while(head != NULL)
cout << head->data << " ", head = head->next;
}