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.