Due Date Is Over
Due Date: 15-09-2024
ASSIGNMENT 1
1. Convert Binary Number in a Linked List to Integer
Problem Statement:
The linked list stores binary representation of a number. The value of node in
each linked list is either 0 or 1.
Return decimal representation of the number in linked list (MSB is at head of
linked list).
ï‚· Input format: head= [1, 0, 1]
Output: 5
Explanation: (101) _2 = (5) _10
ï‚· Input format: head=[0]
Output: 0
Approach:
ï‚· Iterate through the non-empty linked list and retrieve digits from linked
list.
ï‚· Convert binary sequence to decimal number.
(101)_2 = (1*2^2) + (0*2^1) + (1*2^0) = (5)_10
Solution
Node curr=head;
int ans=0;
while(curr!=null)
{
ans=(ans*2) + curr->val;
curr=curr->next;
}
return ans;
2 S.RAJASULOCHANA / SNSCT / IT / 23ITT201 – DS / ASS 1
2. Delete N Nodes after M Nodes of a Linked List
Problem statement:
Given head of linked list and two integers, m and n.
Traverse the linked list, keep first m nodes and delete next n nodes. Repeat the
process until you reach the end of linked list and return the head of modified
list.
ï‚· Input format: head=[1,2,3,4,5,6,7,8], m=2, n=3
Output format: [1, 2, 6, 7]
Explanation: Keep m=2 nodes (1, 2), then skip n=3 nodes (3, 4, 5). Again,
keep m=2 nodes (6, 7) and skip node with values 8 as it reached end of linked
list. Head of linked list after removing nodes is returned.
ï‚· Input format : head= [1,2,3,4,5,6,7,8,9,10,11], m=1, n=3
Output format: [1, 5, 9]
Approach:
ï‚· Iterate over first m nodes and curr will point to the current node and
curr1 to the predecessor of curr node. After m iterations, curr1 will point to
mth node.
ï‚· Iterate over next n nodes. After n iterations when curr reaches the nth
node, to delete the nodes between them just change the next pointer of curr1 to
curr.
3 S.RAJASULOCHANA / SNSCT / IT / 23ITT201 – DS / ASS 1
3. Middle element of linked list
Problem Statement:
Given head of linked list, return the middle node of linked list (in case of oddlength
linked list) and return the second middle node if there are two middle
nodes (in case of even-length linked list).
E.g. Odd-length linked list
Even-length linked list
ï‚· Input format: head=[1,2,3,4,5]
Output format: [3, 4, 5]
Explanation: The middle node of the linked list is node 3.
ï‚· Input format: head=[1,2,3,4,5,6]
Output format: [4, 5, 6]
Explanation: Since the list has two middle values 3 and 4, we will return the
second middle node.
Approach 1:
ï‚· Traverse the entire linked list and find the number of nodes.
ï‚· Traverse again from the head of linked list till ((no. of nodes/2)+1).
Approach 2: Fast and Slow Pointer
Starting from head of linked list, while traversing linked list with slow pointer,
make another pointer traverse the list twice as fast.
When fast reaches end of linked list, slow would be at middle node.
4 S.RAJASULOCHANA / SNSCT / IT / 23ITT201 – DS / ASS 1
4. Reverse linked list
Problem Statement:
Given head of linked list, reverse the list and return the reversed list.
ï‚· Input format: head= [1, 2, 3, 4, 5]
Output format: [5, 4, 3, 2, 1]
ï‚· Input format: head= [1,2]
Output format: [2, 1]
ï‚· Input format: head=[]
Output format: []
Approach:
While traversing the linked list, point current element’s next pointer to its
previous element and for that, we should track previous node.
5 S.RAJASULOCHANA / SNSCT / IT / 23ITT201 – DS / ASS 1
5. Merge two sorted lists
Problem Statement:
Given heads of two sorted linked lists-list1 and list2, merge them into one
sorted linked list and return head of the merged list.
ï‚· Input format: list1= [1, 2, 4], list2= [1, 3, 4]
Output format: [1, 1, 2, 3, 4, 4]
ï‚· Input format: list1= [], list2= [0]
Output format: [0]
ï‚· Input format: list1= [], list2= []
Output format: []
Approach:
Create one temporary node and simultaneously traverse elements of both
linked lists one by one and make the temporary node’s next pointer point to the
node with smaller element.
6 S.RAJASULOCHANA / SNSCT / IT / 23ITT201 – DS / ASS 1
6. Remove duplicates from sorted list
Problem Statement:
Given head of sorted linked list, remove duplicates such that each element
appears only once and return sorted list with no duplicates.
ï‚· Input format: head= [1, 1, 2]
Output format: [1, 2]
ï‚· Input format: head=[1, 1, 2, 3, 3]
Output format: [1, 2, 3]
Approach:
Since the list is sorted, compare the current node’s data to next node’s data. If
both are same, point current node’s next to next node’s next node.
