SUBMITTED BY -

NAME – ADITI SHARMA

ROLL NO. – 01301012022
BRANCH – CSE 1
Q1) Find the maximum/minimum elements of linked list
ANS) int findMax(Node* head) {
if (head == nullptr) {
cout << "The list is empty." << endl;
return INT_MIN;
}

int maxElement = head->data;

while (head != nullptr) {

if (head->data > maxElement) {
maxElement = head->data;
}
head = head->next;
}

return maxElement;
}

int findMin(Node* head) {

if (head == nullptr) {
cout << "The list is empty." << endl;
 return INT_MAX;
}

int minElement = head->data;

while (head != nullptr) {

if (head->data < minElement) {
minElement = head->data;
}
head = head->next;
}

return minElement;
}

Q2) Without using any additional linked list, arrange

elements in the given link list such that all even numbers
are placed after odd numbers.
ANS) Node* evenAfterOdd(Node* head) {
if (!head || !head->next) {
return head;
}
Node* oddHead = NULL;
Node* oddTail = NULL;
Node* evenHead = NULL;
Node* evenTail = NULL;

Node* curr = head;

while (curr != NULL) {

if (curr->data % 2 != 0) {
if (!oddHead) {
oddHead = oddTail = curr;
} else {
oddTail->next = curr;
oddTail = curr;
}
} else {
if (!evenHead) {
evenHead = evenTail = curr;
} else {
evenTail->next = curr;
evenTail = curr;
 }
}
curr = curr->next;
}

if (oddTail!=NULL) {
oddTail->next = evenHead;
}

if (evenTail!=NULL) {
evenTail->next = NULL;
}

if (oddHead!=NULL) {
return oddHead;
} else {
return evenHead;
}
}

Q3) Find Union/Intersection of two given linked lists.

Write a function that returns a newlist
ANS) Node* findIntersection(Node* headA, Node* headB) {
 Node* result_head = nullptr;
Node* result_tail = nullptr;

Traverse the first linked list (headA) and add elements to the result
list if they are also in headB
Node* current = headA;
while (current != nullptr) {
if (contains(headB, current->data)) {
if (!contains(result_head, current->data)) {
if (result_head == nullptr) {
result_head = new Node(current->data);
result_tail = result_head;
} else {
result_tail->next = new Node(current->data);
result_tail = result_tail->next;
}
}
}
current = current->next;
}

return result_head;
}
Node* findUnion(Node* headA, Node* headB) {
Node* result_head = nullptr;
Node* result_tail = nullptr;

Node* current = headA;

while (current != nullptr) {
if (!contains(result_head, current->data)) {
if (result_head == nullptr) {
result_head = new Node(current->data);
result_tail = result_head;
} else {
result_tail->next = new Node(current->data);
result_tail = result_tail->next;
}
}
current = current->next;
}

current = headB;
while (current != nullptr) {
if (!contains(result_head, current->data)) {
 if (result_head == nullptr) {
result_head = new Node(current->data);
result_tail = result_head;
} else {
result_tail->next = new Node(current->data);
result_tail = result_tail->next;
}
}
current = current->next;
}

return result_head;
}
Q4) Write a function to delete a given linked list
ANS) void deleteLinkedList(ListNode*& head) {
while (head != nullptr) {
ListNode* temp = head;
head = head->next;
delete temp ;
}
}
Q5) Reverse a given linked list with Iterative solution and
recursive solution
ANS) recursive solution-:
Node *reverseLinkedListRec(Node *head)
{

if(head==NULL|| head->next==NULL){
return head;
}

Node *temp=reverseLinkedListRec(head->next);
Node*small=temp;
while(small->next!=NULL){

small=small->next;
}
small->next=head;
head->next=NULL;
return temp;

}
Iterative solution -:
Node *reverseLinkedListiter(Node *head) {

Node* pr=NULL;
Node* temp=head;
Node* fd=temp->next;
if(head==NULL || head->next==NULL){
return head;
}

while(temp!=NULL){
fd=temp->next;
temp->next=pr;
pr=temp;
temp=fd;
}

return pr;
}

Q6) Reverse a given link list by using atmost two extra

pointers
ANS) Node *reverseLinkedList(Node *head) {

Node* pr=NULL;
Node* temp=head;
Node* fd=temp->next;
if(head==NULL || head->next==NULL){
return head;
}

while(temp!=NULL){
fd=temp->next;
temp->next=pr;
pr=temp;
temp=fd;
}

return pr;
}

Q7) Delete n nodes after m nodes of a given linked list.

ANS) Node* deleteNNodesAfterMNodes(Node* head, int m, int n) {
if (head == nullptr) {
 return nullptr;
}

Node* current = head;

Node* prev = nullptr;

int mCount = 0;
while (current != nullptr && mCount < m) {
prev = current;
current = current->next;
mCount++;
}

int nCount = 0;
while (current != nullptr && nCount < n) {
Node* temp = current;
current = current->next;
delete temp;
nCount++;
}
 prev->next = current;

deleteNNodesAfterMNodes(current, m, n);

return head;
}

Q8) Add 1 to a number represented as a linked list and

create new link list as shown in below figure
ANS) Node *reverseLinkedListRec(Node *head)
{

if(head==NULL|| head->next==NULL){
return head;
}

Node *temp=reverseLinkedListRec(head->next);
Node*small=temp;
while(small->next!=NULL){

small=small->next;
}
 small->next=head;
head->next=NULL;
return temp;

}
Node* addOneToLinkedList(Node* head) {

Node* reversedHead = reverseLinkedList(head);

Node* current = reversedHead;
Node* prev = nullptr;
int carry = 1;

while (current != nullptr) {

int sum = current->data + carry;
carry = sum / 10;
current->data = sum % 10;
prev = current;
current = current->next;
}

if (carry > 0) {
prev->next = new Node(carry);
 }
return reverseLinkedList(reversedHead);
}

Q9) Reverse the link list in pair wise. Example A-B-C-D-

NULL will be B-A-D-C-NULL
ANS) Node* reverseInPairs(Node* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}

Node* newHead = head->next;

Node* prev = nullptr;
Node* current = head;

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

Node* nextNode = current->next;
current->next = nextNode->next;
nextNode->next = current;

if (prev != nullptr) {
prev->next = nextNode;
 }

prev = current;
current = current->next;
}

return newHead;
}

Q10) Reverse a linked list in groups of given size K (as

shown in figure for K=2)
ANS) Node* reverseInGroups(Node* head, int K) {
Node* current = head;
Node* prev = nullptr;
Node* next = nullptr;
int count = 0;

Node* temp = head;

while (temp != nullptr && count < K) {
temp = temp->next;
count++;
}
 if (count < K) {
return head;
}

while (current != nullptr && count > 0) {

next = current->next;
current->next = prev;
prev = current;
current = next;
count--;
}

if (next != nullptr) {
head->next = reverseInGroups(next, K);
}

return prev;
}
Q11) Find the Kth element from the end of a given linked
list.
ANS) Node* findKthFromEnd(Node* head, int K) {
if (head == nullptr || K <= 0) {
return nullptr;
}

Node* slowPtr = head;

Node* fastPtr = head;

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

if (fastPtr == nullptr) {
return nullptr;
}
fastPtr = fastPtr->next;
}

while (fastPtr != nullptr) {

slowPtr = slowPtr->next;
fastPtr = fastPtr->next;
 }

return slowPtr;
}

Q12) Two singly-linked lists of unequal lengths are given.

Given link lists are joined in Y shape. Find out at which
node they are joined.
ANS) Node* findIntersection(Node* headA, Node* headB) {
Node* result_head = nullptr;
Node* result_tail = nullptr;

// Traverse the first linked list (headA) and add elements to the result
list if they are also in headB
Node* current = headA;
while (current != nullptr) {
if (contains(headB, current->data)) {
if (!contains(result_head, current->data)) {
if (result_head == nullptr) {
result_head = new Node(current->data);
result_tail = result_head;
} else {
 result_tail->next = new Node(current->data);
result_tail = result_tail->next;
}
}
}
current = current->next;
}

return result_head;
}

Q13) Given 2 sorted linked lists - merge them. Make sure

you don't have duplicates in the merged list. The input
lists could have duplicates within them or across the 2
lists.
ANS) Node* mergeTwoSortedLinkedLists(Node* head1, Node* head2)
{

Node* resultHead = nullptr;

Node* resultTail = nullptr;

while (head1 != nullptr && head2 != nullptr) {

if (head1->data < head2->data) {

if (resultTail == nullptr || resultTail->data != head1->data) {

Node* newNode = new Node(head1->data);

if (resultHead == nullptr) {
resultHead = newNode;
resultTail = newNode;
} else {
resultTail->next = newNode;
resultTail = newNode;
}
}
head1 = head1->next;
} else if (head2->data < head1->data) {

if (resultTail == nullptr || resultTail->data != head2->data) {

Node* newNode = new Node(head2->data);

if (resultHead == nullptr) {
resultHead = newNode;
resultTail = newNode;
 } else {
resultTail->next = newNode;
resultTail = newNode;
}
}
head2 = head2->next;
} else {

if (resultTail == nullptr || resultTail->data != head1->data) {

Node* newNode = new Node(head1->data);
if (resultHead == nullptr) {
resultHead = newNode;
resultTail = newNode;
} else {
resultTail->next = newNode;
resultTail = newNode;
}
}
head1 = head1->next;
head2 = head2->next;
}
}
while (head1 != nullptr) {
if (resultTail == nullptr || resultTail->data != head1->data) {
Node* newNode = new Node(head1->data);
if (resultHead == nullptr) {
resultHead = newNode;
resultTail = newNode;
} else {
resultTail->next = newNode;
resultTail = newNode;
}
}
head1 = head1->next;
}

while (head2 != nullptr) {

if (resultTail == nullptr || resultTail->data != head2->data) {

Node* newNode = new Node(head2->data);

if (resultHead == nullptr) {
resultHead = newNode;
 resultTail = newNode;
} else {
resultTail->next = newNode;
resultTail = newNode;
}
}
head2 = head2->next;
}

return resultHead;
}

Q14) Find the 3rd largest element in a given link list.

ANS) int findThirdLargest(Node* head) {
int firstLargest = INT_MIN;
int secondLargest = INT_MIN;
int thirdLargest = INT_MIN;

while (head != nullptr) {

int data = head->data;

if (data > firstLargest) {

 thirdLargest = secondLargest;
secondLargest = firstLargest;
firstLargest = data;
} else if (data > secondLargest && data != firstLargest) {
thirdLargest = secondLargest;
secondLargest = data;
} else if (data > thirdLargest && data != secondLargest && data !=
firstLargest) {
thirdLargest = data;
}

head = head->next;
}

if (thirdLargest != INT_MIN) {
return thirdLargest;
} else {
return -1;
}
}

Q15) Delete last occurrence of an item from a given

linked list
ANS) Node* deleteLastOccurrence(Node* head, int target) {
if (head == nullptr) {
return nullptr;
}

Node* prevToDelete = nullptr;

Node* toDelete = nullptr;
Node* current = head;

while (current != nullptr) {

if (current->data == target) {
prevToDelete = toDelete;
toDelete = current;
}
current = current->next;
}

if (toDelete == nullptr) {
return head;
}

if (prevToDelete == nullptr) {
 head = head->next;
delete toDelete;
return head;
}

prevToDelete->next = toDelete->next;
delete toDelete;

return head;
}

Q16) Find out whether a linked list has a cycle or not? If

there is cycle then find the node at which the loop starts?
Also remove the cycle.
ANS) Node* detectAndRemoveCycle(Node* head) {
Node* slowPtr = head;
Node* fastPtr = head;
bool hasCycle = false;

while (fastPtr != nullptr && fastPtr->next != nullptr) {

slowPtr = slowPtr->next;
fastPtr = fastPtr->next->next;
 if (slowPtr == fastPtr) {
hasCycle = true;
break;
}
}

if (!hasCycle) {
return nullptr;
}

slowPtr = head;
while (slowPtr != fastPtr) {
slowPtr = slowPtr->next;
fastPtr = fastPtr->next;
}

Node* cycleStartNode = slowPtr;

while (fastPtr->next != cycleStartNode) {
fastPtr = fastPtr->next;
}
fastPtr->next = nullptr;
 return cycleStartNode;
}

Q18) Find the middle element of a given linked list without using any
integer variables.
ANS) Node* findMiddle(Node* head) {
if (head == nullptr || head->next == nullptr) {
return head; // Return the head if the list is empty or has only one
element
}

Node* slowPtr = head;

Node* fastPtr = head;

// Move the slow pointer one step at a time, and the fast pointer two
steps at a time
// When the fast pointer reaches the end, the slow pointer will be at
the middle
while (fastPtr != nullptr && fastPtr->next != nullptr) {
slowPtr = slowPtr->next;
fastPtr = fastPtr->next->next;
}
 return slowPtr; // Return the middle element
}

Q20) If a pointer is given to a node in a singly linked list

then delete that particular node
ANS) void deleteNode(Node* nodeToDelete) {
if (nodeToDelete == nullptr || nodeToDelete->next == nullptr) {
return; // Cannot delete if the node is nullptr or the last node
}

Node* temp = nodeToDelete->next;

nodeToDelete->data = temp->data;
nodeToDelete->next = temp->next;
delete temp;
}

Q21) Delete alternate nodes in the given linked list.

ANS) void deleteAlt(struct Node *head){
if(head==NULL){
return ;
}
 while( head!=NULL &&head->next !=NULL){
Node *temp=head->next;
head->next=temp->next;

delete temp;
head=head->next;
}
}

Q22) Delete the sub-sequences (nodes) of linked list

whose sum is equal to zero
ANS) Node* deleteZeroSumSublists(Node* head) {
Node* dummy = new Node(0); // Create a dummy node to handle
the case of the first node
dummy->next = head;
Node* current = dummy;
int sum = 0;

while (current) {
sum += current->data;

if (sum == 0) {
 // A subsequence with a sum of zero found, delete nodes in
between
Node* temp = dummy->next;
while (temp != current) {
sum -= temp->data; // Subtract the node's value from the sum
temp = temp->next;
}
dummy->next = current->next;
}

current = current->next;
}

return dummy->next;
}