1.
Cycle Detection
A linked list is said to contain a cycle if any node is visited more than once while traversing
the list. Given a pointer to the head of a linked list, determine if it contains a cycle. If it
does, return 1. Otherwise, return 0.
CODE:
bool has_cycle(SinglyLinkedListNode* head) {
struct SinglyLinkedListNode* slow=head, * fast=head;
while((slow!=NULL)&&(fast!=NULL)&&(fast->next!=NULL))
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
return 1;
}
return 0;
}
OUTPUT:
1
[Link] Brackets
Given strings of brackets, determine whether each sequence of brackets is balanced. If a string is
balanced, return YES. Otherwise, return NO.
CODE:
char* isBalanced(char* s) {
// Stack to store opening brackets
char stack[1024];
int top = -1;
// Iterate over each character in the string
for (int i = 0; s[i] != '\0'; i++) {
char c = s[i];
if (c == '(' || c == '{' || c == '[') {
// Push opening brackets onto the stack
stack[++top] = c;
} else if (c == ')' || c == '}' || c == ']') {
// If stack is empty, return "NO"
if (top == -1) {
return "NO";
}
// Check if the top of the stack matches the current closing bracket
char top_char = stack[top--];
if ((c == ')' && top_char != '(') ||
(c == '}' && top_char != '{') ||
(c == ']' && top_char != '[')) {
return "NO";
}
}
}
// If the stack is empty, the brackets are balanced
2
return (top == -1) ? "YES" : "NO";
}
OUTPUT:
[Link] Tour
Suppose there is a circle. There are N petrol pumps on that circle. Petrol pumps are numbered 0
to N-1 (both inclusive). You have two pieces of information corresponding to each of the petrol
pump: (1) the amount of petrol that particular petrol pump will give, and (2) the distance from that
petrol pump to the next petrol pump. Initially, you have a tank of infinite capacity carrying no
petrol. You can start the tour at any of the petrol pumps. Calculate the first point from where the
truck will be able to complete the circle. Consider that the truck will stop at each of the petrol
pumps. The truck will move one kilometre for each litre of the petrol.
CODE:
int truckTour(int petrolpumps_rows, int petrolpumps_columns, int** petrolpumps) {
int start = 0; // Start index
int current_balance = 0; // Current petrol balance
int total_balance = 0; // Total petrol balance
for (int i = 0; i < petrolpumps_rows; i++) {
int petrol = petrolpumps[i][0];
int distance = petrolpumps[i][1];
3
current_balance += petrol - distance;
total_balance += petrol - distance;
// If the current balance is negative, reset the start point
if (current_balance < 0) {
start = i + 1; // Move start to the next pump
current_balance = 0; // Reset current balance
}
}
// If total balance is non-negative, return the start point
return total_balance >= 0 ? start : -1;
OUTPUT:
4
4. Delete duplicate-value nodes from a sorted linked list.
You are given the pointer to the head node of a sorted linked list, where the data in the nodes is in
ascending order. Delete nodes and return a sorted list with each distinct value in the original list.
The given head pointer may be null indicating that the list is empty.
CODE:
SinglyLinkedListNode* removeDuplicates(SinglyLinkedListNode* llist) {
if (llist == NULL) return llist; // Check if the list is empty
SinglyLinkedListNode* currBoi = llist; // Current node
SinglyLinkedListNode* nextBoi = currBoi->next; // Next node
// Traverse the list and remove duplicates
while (nextBoi != NULL) {
if (currBoi->data == nextBoi->data) { // Found a duplicate
SinglyLinkedListNode* temp = nextBoi;
nextBoi = nextBoi->next; // Skip the duplicate node
currBoi->next = nextBoi; // Connect current node to nextBoi
free(temp); // Free the duplicate node
} else {
currBoi = currBoi->next; // Move to the next node
nextBoi = nextBoi->next; // Move to the next next node
}
}
return llist; // Return the modified list
5
OUTPUT:
[Link] two sorted linked lists
Given pointers to the heads of two sorted linked lists, merge them into a single, sorted linked list.
Either head pointer may be null meaning that the corresponding list is empty.
Code:
SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode*
head2) {
SinglyLinkedList *newHead = malloc(sizeof(SinglyLinkedList));
newHead->head = NULL;
newHead->tail = NULL;
while(head1 != NULL && head2 != NULL){
if(head1->data > head2->data){
insert_node_into_singly_linked_list(&newHead, head2->data);
head2 = head2->next;
}
else if(head1->data < head2->data){
insert_node_into_singly_linked_list(&newHead, head1->data);
6
head1 = head1->next;
}
else{
insert_node_into_singly_linked_list(&newHead, head1->data);
insert_node_into_singly_linked_list(&newHead, head2->data);
head1 = head1->next;
head2 = head2->next;
}
}
while(head1 != NULL){
insert_node_into_singly_linked_list(&newHead, head1->data);
head1 = head1->next;
}
while(head2 != NULL){
insert_node_into_singly_linked_list(&newHead, head2->data);
head2 = head2->next;
}
return newHead->head;
}
OUTPUT: