Cycle Detection and Removal (Will Not Come Most Likely)
///
Delete Nodes
//Given a singly linked list delete all nodes which are having a greater value among any of the nodes residing on the right side.
//
//Input Format
//First line contains N, the number of nodes in the linked list.
//Next line contains the N nodes data .
//
//Constraints
//0<N<10^9
//
//Output Format
//Print the linked list after deleting the nodes which are having a greater value on right side.
//
//Sample Input
//8
//12 15 10 11 5 6 2 3
//Sample Output
//15 11 6 3
//Explanation
//In the given case 12 is having right node greater than itself i.e. 12<15 so delete it.
//Similarly, 10<11, 5<6 and 2<3 so delete 10, 5 and 2 as well.
//Thus, linked list becomes 15->11->6->3.
#include<iostream>
using namespace std;
class Node{
public:
int data;
Node* next;
Node(int data){
this->data = data;
next = NULL;
}
};
void insertAtEnd(Node * &head, int data){
if(head == NULL) {
head = new Node(data);
return;
}
Node * temp = head;
while(temp->next){
temp = temp->next;
}
temp->next = new Node(data);
}
bool toDel(Node * head){
Node * temp = head->next;
int val = head->data;
while(temp){
if(temp->data > val) return true;
temp = temp->next;
}
return false;
}
int main () {
int n; cin >> n;
Node * head = NULL;
for(int i = 0;i<n;i++){
int val; cin >> val;
insertAtEnd(head,val);
}
Node * temp = head, *prev = NULL;
while(temp){
bool todel = toDel(temp);
if(todel){
if(prev == NULL){
head = temp->next;
}
else{
prev->next = temp->next;
}
}
else{
prev = temp;
}
temp = temp->next;
}
while(head){
cout << head->data << " ";
head = head->next;
}
cout << endl;
return 0;
}
Kth Element from last in linked list
#include<iostream>
using namespace std;
//Given a linked list with n nodes. Find the kth element from last without computing the length of the linked list.
//
//Input Format
//First line contains space separated integers representing the node values of the linked list. The list ends when the input comes as '-1'. The next line contains a single integer k.
//
//Constraints
//n < 10^5
//
//Output Format
//Output a single line containing the node value at the kth element from last.
//
//Sample Input
//1 2 3 4 5 6 -1
//3
//Sample Output
//4
//Explanation
//The linked list is 1 2 3 4 5 6. -1 is not included in the list. So the third element from the last is 4
class Node{
public:
int data;
Node * next;
Node(int data){
this->data = data;
next = NULL;
}
};
void insertAtEnd(Node*& head, int data) {
Node* newNode = new Node(data);
if (head == NULL) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}
void KthNode(Node* head, int n) {
if (head == NULL || n <= 0) return;
Node* slow = head, *fast = head;
for (int i = 0; i < n; i++) {
if (fast == NULL) return;
fast = fast->next;
}
if (fast == NULL) {
cout << n << endl;
return;
}
while (fast->next) {
fast = fast->next;
slow = slow->next;
}
cout << slow->next->data << endl;
}
int main() {
Node* head = NULL;
int n;
while(cin >> n && n != -1){
insertAtEnd(head, n);
}
int k; cin >> k;
KthNode(head, k);
return 0;
}
LinkedList K append
//Given a linked list of length N and an integer K , append the last K elements of a linked list to the front. Note that K can be greater than N.
//
//Input Format
//First line contains a single integer N denoting the size of the linked list.
//Second line contains N space separated integers denoting the elements of the linked list.
//Third line contains a single integer K denoting the number of elements that are to be appended.
//
//Constraints
//1 <= N <= 10^4
//1 <= K <= 10^4
//
//Output Format
//Display all the elements in the modified linked list.
//
//Sample Input
//7
//1 2 2 1 8 5 6
//3
//Sample Output
//8 5 6 1 2 2 1
//Explanation
//Initially the linked list is
//1→ 2→ 3 → 4 → 5 → 6→ null
//and k = 2. After appending the last two elements to the front , the new linked list looks like
//5→ 6→ 1→ 2→ 3 → 4 → null
#include<iostream>
using namespace std;
class Node{
public:
int data;
Node * next;
Node(int data){
this->data = data;
next = NULL;
}
};
void insertAtEnd(Node * &head, int data){
if(head == NULL){
head = new Node(data);
return;
}
Node * temp = head;
while(temp->next){
temp = temp->next;
}
temp->next = new Node(data);
}
int main() {
Node * head = NULL;
int n; cin >> n;
for(int i=0;i<n;i++){
int val; cin >> val;
insertAtEnd(head,val);
}
int k; cin >> k;
if(!head) return 0;
Node * temp = head;
while(temp->next) temp = temp->next;
temp->next = head;
k %= n;
for(int i=0;i<n-k;i++) temp = temp->next;
head = temp->next;
temp->next = NULL;
while(head){
cout << head->data << " ";
head = head->next;
}
return 0;
}
Linked List K reverse
//Given a head to Linked List L, write a function to reverse the list taking k elements at a time. Assume k is a factor of the size of List.
//
//You need not have to create a new list. Just reverse the old one using head.
//
//Input Format
//The first line contains 2 space separated integers N and K
//
//The next line contains N space separated integral elements of the list.
//
//Constraints
//0 <= N <= 10^6 0 <= K <= 10^6
//
//Output Format
//Display the linkedlist after reversing every k elements
//
//Sample Input
//9 3
//9 4 1 7 8 3 2 6 5
//Sample Output
//1 4 9 3 8 7 5 6 2
//Explanation
//N = 9 & K = 3
//
//Original LL is : 9 -> 4 -> 1 -> 7 -> 8 -> 3 -> 2 -> 6 -> 5
//
//After k Reverse : 1 -> 4 -> 9 -> 3 -> 8 -> 7 -> 5 -> 6 -> 2
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int data) {
this->data = data;
next = NULL;
}
};
void insertAtEnd(Node*& head, int data) {
if (head == NULL) {
head = new Node(data);
return;
}
Node* temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = new Node(data);
}
Node* reverse(Node* head, int k) {
if (!head || k <= 0) return head;
Node* prev = NULL, *curr = head, *next = NULL;
int count = 0;
while (curr && count < k) {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
count++;
}
if (next) head->next = reverse(next, k);
return prev;
}
int main() {
int n;
cin >> n;
int k;
cin >> k;
Node* head = NULL;
for (int i = 0; i < n; i++) {
int val;
cin >> val;
insertAtEnd(head, val);
}
head = reverse(head, k);
while (head) {
cout << head->data << " ";
head = head->next;
}
return 0;
}
Merge Sort for linkedlist
//Given a linked list, sort it using the merge sort algorithm.
//
//Input Format
//First line of input contains integer N, denoting the size of the linked list. Next line of input contains N space separated integers denoting the elements of the linked list.
//
//Constraints
//1<=N<=10^3
//
//Output Format
//Print the elements of the linked list after sorting.
//
//Sample Input
//5
//5 4 3 2 1
//Sample Output
//1 2 3 4 5
//Explanation
//5 4 3 2 1 will become 1 2 3 4 5 after sorting.
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
class Node{
public:
int data;
Node * next;
Node(int data){
this->data = data;
next = NULL;
}
};
void insertAtEnd(Node *& head, int data){
if(head == NULL){
head = new Node(data);
return;
}
Node * temp = head;
while(temp->next){
temp = temp->next;
}
temp->next = new Node(data);
}
Node* merge(Node * a, Node * b){
Node * res = NULL;
if(a == NULL) return b;
if(b == NULL) return a;
if(a->data <= b->data){
res = a;
res->next = merge(a->next,b);
}
else{
res = b;
res->next = merge(a,b->next);
}
return res;
}
Node* mergeSort(Node * head){
if(head == NULL || head->next == NULL) return head;
Node * slow = head, *fast = head->next;
while(fast && fast->next){
slow = slow->next;
fast = fast->next->next;
}
Node * second = slow->next;
slow->next = NULL;
Node * left = mergeSort(head);
Node * right = mergeSort(second);
return merge(left,right);
}
int main () {
int n; cin >> n;
Node * head = NULL;
for(int i=0;i<n;i++){
int val; cin >> val;
insertAtEnd(head,val);
}
head = mergeSort(head);
while(head){
cout << head->data << " ";
head = head->next;
}
return 0;
}
Sum of 2 LinkedList
//Given two numbers represented by two linked lists, write a program that prints the sum list. The sum list is linked list representation of addition of two input numbers in linked lists. It is not allowed to modify the lists. Also, not allowed to use explicit extra space (Use Recursion).
//
//Input Format
//First line contains N,M, number of nodes in the 1st and 2nd list.
//Next line contains N nodes of 1st list.
//Next line contains M nodes of 2nd list.
//
//Constraints
//0<N<10^6
//
//Output Format
//Print the sum list after adding the two linked lists.
//
//Sample Input
//3 3
//5 6 3
//8 4 2
//Sample Output
//1 4 0 5
//Explanation
// After adding the two numbers represented by linked lists i.e. 563 + 842 =1405 is represented as sum list. Sum list =1 -> 4 -> 0 -> 5.
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
class Node{
public:
int data;
Node * next;
Node(int data){
this->data = data;
next = NULL;
}
};
void insertAtEnd(Node *& head, int data){
if(head == NULL){
head = new Node(data);
return;
}
Node * temp = head;
while(temp->next){
temp = temp->next;
}
temp->next = new Node(data);
}
Node* addTwoNumbers(Node * l1, Node * l2){
int carry = 0;
stack<int> s1,s2;
while(l1){
s1.push(l1->data); l1 = l1->next;
}
while(l2){
s2.push(l2->data); l2 = l2->next;
}
stack<int> res;
while(!s1.empty() || !s2.empty()){
int sum = 0;
if(!s1.empty()){
sum += s1.top(); s1.pop();
}
if(!s2.empty()){
sum += s2.top(); s2.pop();
}
sum += carry;
carry = sum/10;
res.push(sum%10);
}
if(carry == 1){
res.push(1);
}
Node * head = new Node(0);
Node * temp = head;
while(!res.empty()){
temp->next = new Node(res.top());
res.pop();
temp = temp->next;
}
temp->next = NULL;
return head->next;
}
int main () {
Node *l1 = NULL, *l2 = NULL;
int n, m; cin >> n >> m;
for(int i=0;i<n;i++){
int val; cin >> val;
insertAtEnd(l1,val);
}
for(int i=0;i<m;i++){
int val; cin >> val;
insertAtEnd(l2,val);
}
Node * ans = addTwoNumbers(l1,l2);
while(ans){
cout << ans->data << " ";
ans = ans->next;
}
return 0;
}
Triplet From 3 Linked Lists
//Given three linked lists, say a, b and c, find one node from each list such that the sum of the values of the nodes is equal to a given number say, Target. As any number of answers can be possible return the first one you get while traversing.
//
//Input Format
//The First Line contains 3 Integers n, m and k as the Size of the Three LinedLists. Next 3 Lines contains n, m and k integers Respectively as the elements of Linked Lists. Next Line contains the an Integer as Target.
//
//Constraints
//The Size of the Lists can be different.
//
//Output Format
//Display the 3 elements from each of the Lists whose sum is equals to the target separated by space.
//
//Sample Input
//3 3 3
//12 6 29
//23 5 8
//90 20 59
//101
//Sample Output
//6 5 90
//Explanation
//In the Given Sample Input, 6, 5 and 90 from lists 1, 2 and 3 respectively add to give 101.
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int data){
this->data = data;
next = NULL;
}
};
void insertAtEnd(Node*& head, int val) {
Node* newNode = new Node(val);
if (!head) {
head = newNode;
return;
}
Node* temp = head;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}
void findNodes(Node* head1, Node* head2, Node* head3, int target) {
Node* ptr1 = head1;
while (ptr1) {
Node* ptr2 = head2;
while (ptr2) {
Node* ptr3 = head3;
while (ptr3) {
int sum = ptr1->data + ptr2->data + ptr3->data;
if (sum == target) {
cout << ptr1->data << " " << ptr2->data << " " << ptr3->data << endl;
return;
}
ptr3 = ptr3->next;
}
ptr2 = ptr2->next;
}
ptr1 = ptr1->next;
}
}
int main() {
int n, m, o;
cin >> n >> m >> o;
Node* head1 = nullptr, *head2 = nullptr, *head3 = nullptr;
for (int i = 0; i < n; i++) {
int val;
cin >> val;
insertAtEnd(head1, val);
}
for (int i = 0; i < m; i++) {
int val;
cin >> val;
insertAtEnd(head2, val);
}
for (int i = 0; i < o; i++) {
int val;
cin >> val;
insertAtEnd(head3, val);
}
int target;
cin >> target;
findNodes(head1, head2, head3, target);
return 0;
}