Author: akshay

Problem Statement: Given the head of a linked list and an integer val, remove all the nodes of the linked list that have Node.val == val, and return the new head. Examples: Input: head = [1,2,6,3,4,5,6], val = 6Output: [1,2,3,4,5] Input: head = [], val = 1Output: [] Input: head = [7,7,7,7], val = 7Output: [] Constraints: The number of nodes in the list is in the range [0, 10⁴] 1 ≤ Node.val ≤ 50 0 ≤ val ≤ 50 Approach: Use a dummy (sentinel) node before the head to simplify edge cases. Iterate through the list using a pointer.…

Problem Statement: Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null. Examples: Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3Output: Intersected at ‘8’ Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1Output: Intersected at ‘2’ Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2Output: No intersection Constraints: The number of nodes in each list is in…

Problem Statement: Given the head of a singly linked list, return true if it is a palindrome or false otherwise. Examples: Input: head = [1,2,2,1]Output: true Input: head = [1,2]Output: false Constraints: The number of nodes in the list is in the range [1, 105]. 0 next; } int left = 0, right = vals.size() – 1; while (left < right) { if (vals[left++] != vals[right--]) return false; } return true; } }; bool isPalindrome(struct ListNode* head) { int vals[100000], i = 0, left, right; while (head) { vals[i++] = head->val; head = head->next; } left = 0; right =…

Problem Statement: Given head, the head of a linked list, determine if the linked list has a cycle in it. Return true if there is a cycle; otherwise, return false. Examples: Input: head = [3,2,0,-4], pos = 1Output: true Input: head = [1,2], pos = 0Output: true Input: head = [1], pos = -1Output: false Constraints: The number of nodes is in the range [0, 10⁴]. -10⁵ ≤ Node.val ≤ 10⁵ pos is -1 or a valid index in the linked list. Approach: Use Floyd’s Cycle Detection (also called the Tortoise and Hare algorithm). Use two pointers: slow moves one…

Problem Statement: Given head, the head of a linked list, determine if the linked list has a cycle in it. Return true if there is a cycle; otherwise, return false. Examples: Input: head = [3,2,0,-4], pos = 1Output: true Input: head = [1,2], pos = 0Output: true Input: head = [1], pos = -1Output: false Constraints: The number of nodes is in the range [0, 10⁴]. -10⁵ ≤ Node.val ≤ 10⁵ pos is -1 or a valid index in the linked list. Approach: Use a Set to track visited nodes. While traversing, if we encounter a node already in the…

Problem Statement: Given the head of a singly linked list, reverse the list, and return the reversed list. Examples: Input: head = [1,2,3,4,5] Output: [5,4,3,2,1] Input: head = [1,2] Output: [2,1] Input: head = [] Output: [] Constraints: The number of nodes in the list is in the range [0, 5000]. -5000 ≤ Node.val ≤ 5000 Approach: Use three pointers: prev, curr, and temp. In each step: Save the next node. Point current node’s next to previous. Move prev and curr forward. Return prev as the new head. Time and Space Complexity: Time Complexity: O(n), where n is the number…

Problem Statement: Find the middle node of a singly linked list using the slow and fast pointer approach. Approach: Use two pointers: slow and fast. Initialize both at the head of the list. Move slow one step and fast two steps at a time. When fast reaches the end, slow will be at the middle. Examples: Input: [1,2,3,4,5] Output: [3,4,5] Explanation: The middle node is node 3. Input: [1,2,3,4,5,6] Output: [4,5,6] Explanation: There are two middle nodes: 3 and 4. We return the second one. Constraints: The number of nodes in the list is in the range [1, 100]. 1…

Linked List A Linked List is a linear data structure in which elements (called nodes) are connected using pointers. Each node contains: A value (the actual data) A reference (or pointer) to the next node (and optionally to the previous node in doubly linked lists) Types of Linked Lists: 1. Singly Linked List value: the data part next: a pointer/reference to the next node It moves only in one direction (forward) Structure: [value | next] -> [value | next] -> [value | null] 2. Doubly Linked List value: the data next: pointer to the next node prev: pointer to the…

Problem Statement: Design and implement a simple singly linked list using basic building blocks like nodes and references (or pointers). The goal is to: Define a node with a value and a pointer to the next node. Create individual nodes and link them together to form a list. Traverse the list from the head and print each node’s value. This helps you understand how data is stored and accessed sequentially in memory using pointers or references. Example: Input: Create 3 nodes with values 10, 20, 30 and link them in order. Output: Print values in sequence: 10 20 30 Approach:…

What is Merge Sort? Merge Sort is a popular divide-and-conquer sorting algorithm that divides the input array into two halves, recursively sorts them, and then merges the sorted halves into one sorted result. It is an example of a stable sort that guarantees O(n log n) performance in all cases — best, worst, and average. Approach: Divide & Conquer Divide: Split the array into two halves. Conquer: Recursively sort each half using merge sort. Combine: Merge the two sorted halves into one sorted array. Key Concept: Merge Step The key step is merging two sorted arrays efficiently into one sorted…