DS week 4 Solution

In-lab:

1. Middle of the Linked List

Link: https://leetcode.com/problems/middle-of-the-linked-list/description/

Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example 1:

Input: head = [1,2,3,4,5]

Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Example 2:

Input: head = [1,2,3,4,5,6]

Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Constraints:

 The number of nodes in the list is in the range [1, 100].

 1 <= Node.val <= 100

Program: -

struct ListNode* middleNode(struct ListNode* head) {

struct ListNode *t1=head,*t2=head;
if(head==NULL || head->next==NULL)
{
return head;
}
while(t2 && t2->next)
 {
t1=t1->next;
t2=t2->next->next;
}
return t1;
}

2. Linked List Cycle

Link: https://leetcode.com/problems/linked-list-cycle/description/

Given head, the head of a linked list, determine if the linked list has a cycle in it.

There is a cycle in a linked list if there is some node in the list that can be reached again by
continuously following the next pointer. Internally, pos is used to denote the index of the node
that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1

Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-
indexed).

Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1

Output: false
Explanation: There is no cycle in the linked list.

Constraints:

 The number of the nodes in the list is in the range [0, 10 ].

4

 -10 <= Node.val <= 10

5 5

 pos is -1 or a valid index in the linked-list.

Program: -

bool hasCycle(struct ListNode *head) {

struct ListNode *t1=head, *t2;
if(!head)
return false;
t2=head->next;
while(t1&&t2&&t2->next)
{
if(t1==t2)
return true;
t1=t1->next;
t2=t2->next->next;
}
return false;
}

3. Remove Friends

After getting her PhD, Christie has become a celebrity at her university, and her
facebook profile is full of friend requests. Being the nice girl she is, Christie has
accepted all the requests. Now Kuldeep is jealous of all the attention she is
getting from other guys, so he asks her to delete some of the guys from her
friend list. To avoid a 'scene', Christie decides to remove some friends from her
friend list, since she knows the popularity of each of the friend she has, she uses
the following algorithm to delete a friend. Algorithm Delete(Friend):
DeleteFriend=false for i = 1 to Friend.length-1 if (Friend[i].popularity <
Friend[i+1].popularity) delete i th friend DeleteFriend=true break if(DeleteFriend
== false) delete the last friend

Input Format
 First line contains T number of test cases. First line of each test case
contains N, the number of friends Christie currently has and K, the
number of friends Christie decides to delete. Next lines contains
popularity of her friends separated by space.

Constraints
 1<=T<=1000

 1<=N<=100000

 0<=K< N

 0<=popularity_of_friend<=100

 NOTE: Order of friends after deleting exactly K friends should be

maintained as given in input.

Output Format
 For each test case print N-K numbers which represent popularity of
Christie friend's after deleting K friends.

Sample Input 0
3
31
3 100 1
52
19 12 3 4 17
53
23 45 11 77 18

Sample Output 0
100 1
19 12 17
77 18
Program:

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <stdlib.h>

void deleteFriends(int friends[], int n, int k) {

int i, j;

for (i = 0; i < k; i++) {

int deleteFriend = 0;

for (j = 0; j < n - 1; j++) {

if (friends[j] < friends[j + 1]) {

for (int l = j; l < n - 1; l++) {

friends[l] = friends[l + 1];

n--;

deleteFriend = 1;

break;

if (!deleteFriend) {

n--;

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

printf("%d ", friends[i]);

printf("\n");
}

int main() {

int t;

scanf("%d", &t);

while (t--) {

int n, k;

scanf("%d %d", &n, &k);

int friends[n];

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

scanf("%d", &friends[i]);

deleteFriends(friends, n, k);

return 0;

OR

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <stdlib.h>

void deleteFriends(int friends[], int n, int k) {

int i, j;

for (i = 0; i < k; i++) {

 int deleteFriend = 0;

for (j = 0; j < n - 1; j++) {

if (friends[j] < friends[j + 1]) {

for (int l = j; l < n - 1; l++) {

friends[l] = friends[l + 1];

n--;

deleteFriend = 1;

break;

if (!deleteFriend) {

n--;

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

printf("%d ", friends[i]);

printf("\n");

int main() {

int t;

scanf("%d", &t);

while (t--) {

int n, k;

scanf("%d %d", &n, &k);

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

scanf("%d", &friends[i]);

deleteFriends(friends, n, k);

return 0;

Post-Lab:

1.Write a C program to implement Single Linked List. (all operations).

#include <stdio.h>

#include <stdlib.h>

// Define the structure of a node

struct Node {

int data;

struct Node* next;

};

// Function to insert a node at the beginning of the linked list

void insertAtBeginning(struct Node** head_ref, int new_data) {

// Allocate memory for new node

struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

// Assign data to new node

new_node->data = new_data;

// Link the new node to the current head

new_node->next = *head_ref;

// Update the head to point to the new node

*head_ref = new_node;
}

// Function to insert a node after a given node

void insertAfter(struct Node* prev_node, int new_data) {

if (prev_node == NULL) {

printf("Previous node cannot be NULL");

return;

// Allocate memory for new node

struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

// Assign data to new node

new_node->data = new_data;

// Link the new node to the next of previous node

new_node->next = prev_node->next;

// Link the previous node to the new node

prev_node->next = new_node;

// Function to insert a node at the end of the linked list

void insertAtEnd(struct Node** head_ref, int new_data) {

// Allocate memory for new node

struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

struct Node* last = *head_ref;

// Assign data to new node

new_node->data = new_data;

// Since the new node is going to be the last node, make next of it as NULL

new_node->next = NULL;

// If the linked list is empty, then make the new node as head

if (*head_ref == NULL) {

*head_ref = new_node;

return;
 }

// Else traverse till the last node

while (last->next != NULL)

last = last->next;

// Change the next of last node

last->next = new_node;

return;

// Function to delete a node by key

void deleteNodeByKey(struct Node** head_ref, int key) {

// Store head node

struct Node* temp = *head_ref, *prev;

// If head node itself holds the key to be deleted

if (temp != NULL && temp->data == key) {

*head_ref = temp->next;

free(temp);

return;

// Search for the key to be deleted, keep track of the previous node

while (temp != NULL && temp->data != key) {

prev = temp;

temp = temp->next;

// If key was not present in linked list

if (temp == NULL)

return;

// Unlink the node from linked list

prev->next = temp->next;

free(temp);

}
// Function to print the linked list

void printList(struct Node* node) {

while (node != NULL) {

printf("%d ", node->data);

node = node->next;

printf("\n");

int main() {

// Initialize an empty linked list

struct Node* head = NULL;

// Insert some nodes

insertAtEnd(&head, 1);

insertAtBeginning(&head, 2);

insertAtEnd(&head, 3);

insertAfter(head->next, 4);

printf("Linked list: ");

printList(head);

// Delete a node

deleteNodeByKey(&head, 3);

printf("Linked list after deletion: ");

printList(head);

return 0;

2.Find the Middle

You are given the head of a singly linked list A of length N. The values in the list are 1, 2,…,

AN respectively. You need to find the value of the middle element of the linked list.

The middle element of a linked list of length N is the ( [N/2]+1)-th element from the head of the list.

Input Format

The first line of the input contains a single integer T - the number of test cases. The description of T
test

cases follows.

The first line of each test case contains a single integer N.

The second line of each test case contains N space-separated integers 1, 2,…,AN.

Output Format

For each test case, the function you complete should return the value of the middle element of the
list.

Note: You need to complete the function get Middle Element to solve the problem.

Constraints

1≤T≤100

1≤N≤105

1≤Ai≤109 for each valid i

the sum of N over all test cases does not exceed 2 .105

Link:https://www.codechef.com/practice/course/interview-dsa/DSAPREP_08/problems/LLMID

Program:

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <stdlib.h>

struct node

int data;

struct node * next;

}*head=NULL,*tail=NULL;

struct node * createNode(int data)

{

struct node *n=(struct node *)malloc(sizeof(struct node));

n->data=data;

n->next=NULL;

return n;

void addAtEnd(int data)

struct node *n=createNode(data),*t=head;

if(head==NULL)

head=n;

tail=n;

return;

tail->next=n;

tail=n;

struct node * middle()

struct node *t1=head,*t2=head;

if(head==NULL || head->next==NULL)

return head;

while(t2 && t2->next)

t1=t1->next;
 t2=t2->next->next;

return t1;

int main() {

int t,n,x, c;

scanf("%d",&t);

while(t--)

head=NULL;

scanf("%d",&n);

while(n--)

scanf("%d",&x);

addAtEnd(x);

struct node *x=middle();

printf("%d\n",x->data);

return 0;

Skill - Session:

1. Print Linked List

Let's put the learning to use. We already learnt how to traverse a Linked List using a while loop . We
have to keep

two things in mind:

1.Take head as the starting reference.

2.Loop till p is not NULL.

Sanad has a problem, he is a beginner to Linked Lists just like you and he needs your help.

Given a linked list fill the function printList() to print the elements of the list. You have to print each
element of the

list in a new line.

Link: https://www.hackerrank.com/contests/ds-week3/challenges/print-linked-list-2-1

Program: -

#include <stdio.h>

#include <stdlib.h>

// Define a structure for the linked list node

struct Node {

int data;

struct Node* next;

};

// Function to print the elements of the linked list

void printList(struct Node* head) {

// Traverse the linked list using a while loop

struct Node* current = head;

while (current != NULL) {

// Print the current node's data

printf("%d ", current->data);

// Move to the next node

current = current->next;

}
int main() {

int N;

scanf("%d", &N);

// Create the head pointer

struct Node* head = NULL;

struct Node* tail = NULL;

// Create the linked list by taking input from the user

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

int value;

scanf("%d", &value);

// Create a new node

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = value;

newNode->next = NULL;

// If the list is empty, set the new node as the head

if (head == NULL) {

head = newNode;

tail = newNode;

} else {

// Otherwise, add the new node to the end of the list

tail->next = newNode;

tail = newNode;

// Call the printList function to print the elements of the list

printList(head);
 // Free the memory allocated for the linked list nodes

struct Node* temp;

while (head != NULL) {

temp = head;

head = head->next;

free(temp);

return 0;

2. Delete a node in the middle of a single linked list

Given a linkedlist, for example:-

Input:- A->B->C->D->E

you have to delete node C.

Constraint :- You have only access to the node to be deleted (node C).

Output :- A->B->D->E

Link: https://www.hackerrank.com/contests/ds-week4-1/challenges/delete-node-in-linked-list

Program: -

#include <stdio.h>

#include <stdlib.h>

// Define a node structure

struct Node {

int data;

struct Node* next;

};
// Function to insert a node at the end of the list

void append(struct Node** head_ref, int new_data) {

struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

struct Node* last = *head_ref;

new_node->data = new_data;

new_node->next = NULL;

if (*head_ref == NULL) {

*head_ref = new_node;

return;

while (last->next != NULL)

last = last->next;

last->next = new_node;

return;

// Function to delete the middle node of the list

void deleteMiddle(struct Node** head_ref) {

if (*head_ref == NULL || (*head_ref)->next == NULL)

return;

struct Node *slow_ptr = *head_ref, *fast_ptr = *head_ref;

struct Node *prev_ptr = NULL;

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

fast_ptr = fast_ptr->next->next;

prev_ptr = slow_ptr;

slow_ptr = slow_ptr->next;

prev_ptr->next = slow_ptr->next;
 free(slow_ptr);

// Function to print the linked list

void printList(struct Node* node) {

while (node != NULL) {

printf("%c ", node->data);

node = node->next;

printf("\n");

// Main function

int main() {

struct Node* head = NULL;

// Appending elements to the list

append(&head, 'A');

append(&head, 'B');

append(&head, 'C');

append(&head, 'D');

append(&head, 'E');

//printf("Original List: ");

//printList(head);

// Deleting the middle node

deleteMiddle(&head);

//printf("List after deleting middle node: ");

printList(head);
 return 0;

3.Delete Duplicate Nodes from a Linked List

You're given the pointer to the head node of a sorted linked list, where the data in the nodes is in
ascending order.

Delete as few nodes as possible so that the list does not contain any value more than once. The given
head pointer

may be null indicating that the list is empty.

Link: https://www.hackerrank.com/contests/ds-week4-1/challenges/delete-duplicate-nodes-from-a-
linked-list

Program: -

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <stdlib.h>

// Node structure

struct Node {

int data;

struct Node* next;

};

// Function to create a new node

struct Node* createNode(int data) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

 if (newNode == NULL) {

printf("Memory allocation failed!\n");

exit(1);

newNode->data = data;

newNode->next = NULL;

return newNode;

// Function to insert a node at the end of the linked list

void insertAtEnd(struct Node** head, int data) {

struct Node* newNode = createNode(data);

if (*head == NULL) {

*head = newNode;

} else {

struct Node* temp = *head;

while (temp->next != NULL) {

temp = temp->next;

temp->next = newNode;

// Function to delete duplicate nodes from a sorted linked list

void deleteDuplicates(struct Node* head) {

struct Node* current = head;

struct Node* nextNext;

if (current == NULL) {

return;

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

if (current->data == current->next->data) {

nextNext = current->next->next;

free(current->next);

current->next = nextNext;

} else {

current = current->next;

// Function to print the linked list

void printList(struct Node* head) {

struct Node* temp = head;

while (temp != NULL) {

printf("%d ", temp->data);

temp = temp->next;

printf("\n");

// Function to deallocate memory for the linked list

void freeList(struct Node* head) {

struct Node* temp;

while (head != NULL) {

temp = head;

head = head->next;

free(temp);

}
int main() {

struct Node* head = NULL;

// Example usage

insertAtEnd(&head, 1);

insertAtEnd(&head, 2);

insertAtEnd(&head, 2);

insertAtEnd(&head, 3);

insertAtEnd(&head, 3);

insertAtEnd(&head, 4);

deleteDuplicates(head);

printList(head);

freeList(head);

return 0;

4. Moves the last node to the front

Write a function that moves the last node to the front in a given Singly Linked List.
Sample 1:

Input: 1 → 2 → 3 → 4 → 5

Output: 5 → 1 → 2 → 3 → 4

Sample 2:

Input: 3 → 8 → 1 → 5 → 7 → 12

Output: 12 → 3 → 8 → 1 → 5 → 7

Link: https://www.hackerrank.com/contests/ds-week4-1/challenges/moves-the-node

Program:

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <stdlib.h>

// Define the structure of a node

struct Node {

int data;

struct Node* next;

};

// Function to insert a node at the beginning of the linked list

void push(struct Node** head_ref, int new_data) {

// Allocate memory for a new node

struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

// Assign data to the new node

new_node->data = new_data;

// Make the new node point to the current head

new_node->next = *head_ref;
 // Move the head to point to the new node

*head_ref = new_node;

// Function to move the last node to the front

void moveLastToFront(struct Node** head_ref) {

// Check if the list is empty or has only one node

if (*head_ref == NULL || (*head_ref)->next == NULL)

return;

struct Node *last = *head_ref, *second_last = NULL;

// Traverse the list till the last node

while (last->next != NULL) {

second_last = last;

last = last->next;

// Move the last node to the front

second_last->next = NULL;

last->next = *head_ref;

*head_ref = last;

// Function to print the linked list

void printList(struct Node* node) {

while (node != NULL) {

printf("%d ", node->data);

node = node->next;

printf("\n");
}

// Driver program to test above functions

int main() {

struct Node* head = NULL;

// Create a linked list: 1->2->3->4->5

push(&head, 5);

push(&head, 4);

push(&head, 3);

push(&head, 2);

push(&head, 1);

moveLastToFront(&head);

printList(head);

return 0;

5. Create and return a new list

Given two lists sorted in increasing order, create and return a new list representing the intersection
of the two lists.

The new list should be made with its own memory — the original lists should not be changed.

Sample 1:

Input: First linked list: 1 → 2 → 3 → 4 → 6

Second linked list be 2 → 4 → 6 → 8,

Output: 2 → 4 → 6.

The elements 2, 4, 6 are common in both the list so they appear in the intersection list.

Link: https://www.hackerrank.com/contests/ds-week4-1/challenges/create-and-return-a-new-list

Program:

#include <stdio.h>
#include <string.h>

#include <math.h>

#include <stdlib.h>

// Define the structure of a node

struct Node {

int data;

struct Node* next;

};

// Function to insert a node at the end of the linked list

void append(struct Node** head_ref, int new_data) {

// Allocate memory for a new node

struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

// Assign data to the new node

new_node->data = new_data;

new_node->next = NULL;

// If the linked list is empty, make the new node as the head

if (*head_ref == NULL) {

*head_ref = new_node;

return;

// Otherwise, traverse to the last node and append the new node

struct Node* last = *head_ref;

while (last->next != NULL)

last = last->next;
 last->next = new_node;

// Function to find the intersection of two linked lists

struct Node* intersection(struct Node* head1, struct Node* head2) {

struct Node* result = NULL;

struct Node** tail = &result;

// Traverse both lists and find common elements

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

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

append(tail, head1->data);

tail = &((*tail)->next);

head1 = head1->next;

head2 = head2->next;

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

head1 = head1->next;

} else {

head2 = head2->next;

return result;

// Function to print the linked list

void printList(struct Node* node) {

while (node != NULL) {

printf("%d ", node->data);

node = node->next;

}
 printf("\n");

// Driver program to test above functions

int main() {

// Create the first linked list: 1->2->3->4->6

struct Node* head1 = NULL;

append(&head1, 1);

append(&head1, 2);

append(&head1, 3);

append(&head1, 4);

append(&head1, 6);

// Create the second linked list: 2->4->6->8

struct Node* head2 = NULL;

append(&head2, 2);

append(&head2, 4);

append(&head2, 6);

append(&head2, 8);

// Find the intersection of the two lists

struct Node* result = intersection(head1, head2);

// Print the intersection list

printList(result);

return 0;

}
6. Returns the value at the Nth node from the end

Given a Linked List and a number N, write a function that returns the value at the Nth node from the
end of the

Linked List.

Sample 1:

Input: 10 → 20 → 30 → 40 → 50 → None

N=2

Output: 40

Link: https://www.hackerrank.com/contests/ds-week4-1/challenges

Program:

#include <stdio.h>

#include <string.h>

#include <math.h>

#include <stdlib.h>

// Define the structure of a node

struct Node {

int data;

struct Node* next;

};

// Function to insert a node at the beginning of the linked list

void push(struct Node** head_ref, int new_data) {

// Allocate memory for a new node

struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

 // Assign data to the new node

new_node->data = new_data;

// Make the new node point to the current head

new_node->next = *head_ref;

// Move the head to point to the new node

*head_ref = new_node;

// Function to get the Nth node from the end of the linked list

int getNthFromEnd(struct Node* head, int n) {

if (head == NULL)

return -1;

struct Node* first = head;

struct Node* second = head;

// Move the second pointer to the nth node from the beginning

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

if (second == NULL)

return -1; // Out of bounds

second = second->next;

// Move both pointers until the second pointer reaches the end

while (second != NULL) {

first = first->next;

second = second->next;

}
 // At this point, the first pointer is at the nth node from the end

return first->data;

// Driver program to test above functions

int main() {

struct Node* head = NULL;

// Create a linked list: 10->20->30->40->50

push(&head, 50);

push(&head, 40);

push(&head, 30);

push(&head, 20);

push(&head, 10);

int n = 2;

printf("%d\n",getNthFromEnd(head, n));

return 0;