Department Of Computer

Science
Name: Sakhawat Ali

Sap ID: 70151162

Section: 4E

Submitted To: Mam Mishal Muneer

QUESTION #1

#include <iostream>

using namespace std;

class Node {

public:

int data;

Node* next;

Node(int val) {

data = val;

next = NULL;

};

class LinkedList {

public:

Node* head;

LinkedList() { head = NULL; }

void append(int val) {

Node* newNode = new Node(val);

if (head == NULL) {
 head = newNode;

return;

Node* temp = head;

while (temp->next != NULL) {

temp = temp->next;

temp->next = newNode;

void printMultiplesOfK(int k) {

Node* temp = head;

int index = 0;

while (temp != NULL) {

if (index % k == 0) {

cout << temp->data << " -> ";

temp = temp->next;

index++;

cout << "NULL" << endl;

};

int main() {

LinkedList list;
 int n, value, k;

cout << "Enter number of elements: ";

cin >> n;

cout << "Enter elements: ";

for (int i = 0; i < n; i++) {

cin >> value;

[Link](value);

cout << "Enter value of k: ";

cin >> k;

[Link](k);

return 0;

}
QUESTION # 2

#include <iostream>

using namespace std;

class Node {

public:

int data;

Node* next;

Node(int val) {

data = val;

next = NULL;

};
class CircularLinkedList {

public:

Node* head;

CircularLinkedList() { head = NULL; }

void append(int val) {

Node* newNode = new Node(val);

if (head == NULL) {

head = newNode;

newNode->next = head;

return;

Node* temp = head;

while (temp->next != head) {

temp = temp->next;

temp->next = newNode;

newNode->next = head;

void printMultiplesOfK(int k) {

if (head == NULL) return;

Node* temp = head;

int index = 0;

int n = 0;

do {
 n++;

temp = temp->next;

} while (temp != head);

bool visited[n] = {false};

temp = head;

int count = 0;

while (count < n) {

if (!visited[index % n]) {

cout << temp->data << " -> ";

visited[index % n] = true;

count++;

temp = temp->next;

index += k;

cout << "NULL" << endl;

};

int main() {

CircularLinkedList list;

int n, value, k;

cout << "Enter number of elements: ";

cin >> n;
 cout << "Enter elements: ";

for (int i = 0; i < n; i++) {

cin >> value;

[Link](value);

cout << "Enter value of k: ";

cin >> k;

[Link](k);

return 0;

}
QUESTION # 3

#include <iostream>

using namespace std;

class Node {

public:

int data;

Node* next;

Node(int val) {

data = val;

next = NULL;

};

class LinkedList {

public:

Node* head;

LinkedList() { head = NULL; }

void append(int val) {

Node* newNode = new Node(val);

if (head == NULL) {

head = newNode;

return;
 }

Node* temp = head;

while (temp->next != NULL) {

temp = temp->next;

temp->next = newNode;

void reverse() {

Node* prev = NULL;

Node* current = head;

Node* next = NULL;

while (current != NULL) {

next = current->next;

current->next = prev;

prev = current;

current = next;

head = prev;

void removeGreaterRight() {

reverse();

Node* maxNode = head;

Node* temp = head;

while (temp != NULL && temp->next != NULL) {

 if (temp->next->data < maxNode->data) {

temp->next = temp->next->next;

} else {

temp = temp->next;

maxNode = temp;

reverse();

void printList() {

Node* temp = head;

while (temp != NULL) {

cout << temp->data << " -> ";

temp = temp->next;

cout << "NULL" << endl;

};

int main() {

LinkedList list;

int n, value;

cout << "Enter number of elements: ";

cin >> n;
 cout << "Enter elements: ";

for (int i = 0; i < n; i++) {

cin >> value;

[Link](value);

[Link]();

[Link]();

return 0;

}
QUESTION # 4

#include <iostream>

using namespace std;

class Node {

public:

int data;

Node* next;

Node(int val) {

data = val;

next = NULL;

};

class LinkedList {

public:

Node* head;

LinkedList() { head = NULL; }

void append(int val) {

Node* newNode = new Node(val);

if (head == NULL) {

head = newNode;
 return;

Node* temp = head;

while (temp->next != NULL) {

temp = temp->next;

temp->next = newNode;

void removeAlternateNodes() {

if (head == NULL) return;

Node* current = head;

while (current != NULL && current->next != NULL) {

Node* temp = current->next;

current->next = temp->next;

delete temp;

current = current->next;

void printList() {

Node* temp = head;

while (temp != NULL) {

cout << temp->data << " -> ";

temp = temp->next;
 }

cout << "NULL" << endl;

};

int main() {

LinkedList list;

int n, value;

cout << "Enter number of elements: ";

cin >> n;

cout << "Enter elements: ";

for (int i = 0; i < n; i++) {

cin >> value;

[Link](value);

cout << "Original List: ";

[Link]();

[Link]();

cout << "List after removing alternate nodes: ";

[Link]();
 return 0;

QUESTION # 5

#include <iostream>

using namespace std;

class Node {

public:

int data;

Node* next;

Node(int val) {

data = val;

next = NULL;

};
class LinkedList {

public:

Node* head;

LinkedList() { head = NULL; }

void append(int val) {

Node* newNode = new Node(val);

if (head == NULL) {

head = newNode;

return;

Node* temp = head;

while (temp->next != NULL) {

temp = temp->next;

temp->next = newNode;

void findMiddle() {

if (head == NULL) return;

Node* slow = head;

Node* fast = head;

 while (fast != NULL && fast->next != NULL) {

fast = fast->next->next;

slow = slow->next;

cout << slow->data << endl;

};

int main() {

LinkedList list;

int n, value;

cout << "Enter number of elements: ";

cin >> n;

cout << "Enter elements: ";

for (int i = 0; i < n; i++) {

cin >> value;

[Link](value);

cout << "Middle element: ";

[Link]();

return 0;
}

QUESTION # 6

#include <iostream>

using namespace std;

class Node {

public:

char data;

Node* next;

Node(char val) {

data = val;

next = NULL;

};
class LinkedList {

public:

Node* head;

LinkedList() { head = NULL; }

void append(char val) {

Node* newNode = new Node(val);

if (head == NULL) {

head = newNode;

return;

Node* temp = head;

while (temp->next != NULL) {

temp = temp->next;

temp->next = newNode;

bool isPalindrome() {

if (head == NULL) return true;

Node* slow = head;

Node* fast = head;

while (fast != NULL && fast->next != NULL) {

 slow = slow->next;

fast = fast->next->next;

Node* prev = NULL;

Node* current = slow;

Node* nextNode = NULL;

while (current != NULL) {

nextNode = current->next;

current->next = prev;

prev = current;

current = nextNode;

Node* firstHalf = head;

Node* secondHalf = prev;

while (secondHalf != NULL) {

if (firstHalf->data != secondHalf->data) {

return false;

firstHalf = firstHalf->next;

secondHalf = secondHalf->next;

}
 return true;

void printList() {

Node* temp = head;

while (temp != NULL) {

cout << temp->data << " -> ";

temp = temp->next;

cout << "NULL" << endl;

};

int main() {

LinkedList list;

int n;

char value;

cout << "Enter number of elements: ";

cin >> n;

cout << "Enter elements: ";

[Link]();

for (int i = 0; i < n; i++) {

cin >> value;

[Link](value);
 }

if ([Link]()) {

cout << "Palindrome" << endl;

} else {

cout << "Not palindrome" << endl;

return 0;

}
QUESTION # 7
#include <iostream>

using namespace std;

class Node {

public:

int data;

Node* next;

Node(int val) {

data = val;

next = NULL;

};

class LinkedList {

public:

Node* head;

LinkedList() { head = NULL; }

void append(int val) {

Node* newNode = new Node(val);

if (head == NULL) {
 head = newNode;

return;

Node* temp = head;

while (temp->next != NULL) {

temp = temp->next;

temp->next = newNode;

void printFrequency() {

if (head == NULL) return;

Node* temp1 = head;

while (temp1 != NULL) {

int count = 0;

Node* temp2 = head;

bool printed = false;

while (temp2 != temp1) {

if (temp2->data == temp1->data) {

printed = true;

break;

temp2 = temp2->next;
 }

if (!printed) {

temp2 = temp1;

while (temp2 != NULL) {

if (temp2->data == temp1->data) {

count++;

temp2 = temp2->next;

cout << "Freq(" << temp1->data << ") = " << count << endl;

temp1 = temp1->next;

};

int main() {

LinkedList list;

int n, value;

cout << "Enter number of elements: ";

cin >> n;

cout << "Enter elements: ";

for (int i = 0; i < n; i++) {

 cin >> value;

[Link](value);

[Link]();

return 0;

QUESTION # 8
#include <iostream>

using namespace std;

class ListNode {

public:

int val;

ListNode* next;

ListNode(int x) : val(x), next(NULL) {}

};

class LinkedList {

public:

ListNode* head;

LinkedList() : head(NULL) {}

void insert(int val) {

if (!head) {

head = new ListNode(val);

return;

ListNode* temp = head;

while (temp->next) {

temp = temp->next;
 }

temp->next = new ListNode(val);

void duplicate() {

if (!head) return;

ListNode* tail = head;

while (tail->next) {

tail = tail->next;

ListNode* current = head;

ListNode* newHead = NULL;

ListNode* newTail = NULL;

while (current) {

ListNode* newNode = new ListNode(current->val);

if (!newHead) {

newHead = newNode;

newTail = newNode;

} else {

newTail->next = newNode;

newTail = newNode;

current = current->next;
 }

tail->next = newHead;

void print() {

ListNode* temp = head;

while (temp) {

cout << temp->val << " -> ";

temp = temp->next;

cout << "NULL" << endl;

};

int main() {

LinkedList list;

int n, val;

cout << "Enter number of elements: ";

cin >> n;

cout << "Enter elements: ";

for (int i = 0; i < n; i++) {

cin >> val;

[Link](val);

}
 cout << "Original List:" << endl;

[Link]();

[Link]();

cout << "Duplicated List:" << endl;

[Link]();

return 0;