Search Blogs

Showing results for "Dummy Node"

Found 4 results

LeetCode 203: Remove Linked List Elements – Step-by-Step Guide for Beginners

Try the ProblemYou can practice the problem here:https://leetcode.com/problems/remove-linked-list-elements/Problem Description (In Very Simple Words)You are given:The head of a linked listAn integer value valYour task is:👉 Remove all nodes from the linked list whose value is equal to val.👉 Return the updated head of the linked list.What is a Linked List? (Quick Recap)A linked list is a chain of nodes where each node contains:value + pointer to next nodeExample:1 → 2 → 6 → 3 → 4 → 5 → 6 → nullExample WalkthroughExample 1Input:head = [1,2,6,3,4,5,6]val = 6Output:[1,2,3,4,5]ExplanationWe remove all nodes with value 6.1 → 2 → ❌6 → 3 → 4 → 5 → ❌6Final list:1 → 2 → 3 → 4 → 5Example 2Input:head = []val = 1Output:[]Example 3Input:head = [7,7,7,7]val = 7Output:[]All nodes are removed.Constraints0 <= number of nodes <= 10^41 <= Node.val <= 500 <= val <= 50Understanding the Problem DeeplyThe tricky part is:👉 Nodes can appear anywhere:At the beginningIn the middleAt the endOr all nodes👉 Linked list does NOT allow backward traversalSo we must carefully handle pointers.Thinking About the SolutionWhen solving this problem, multiple approaches may come to mind:Possible ApproachesTraverse the list and remove nodes manually.Handle head separately, then process the rest.Use a dummy node to simplify logic.Use recursion (less preferred for beginners).Approach 1: Without Dummy Node (Manual Handling)IdeaFirst, remove nodes from the start (head) if they match val.Then traverse the list using two pointers:prev → previous nodecurr → current nodeKey ChallengeHandling head separately makes code more complex.Codeclass Solution { public ListNode removeElements(ListNode head, int val) { // Step 1: Remove matching nodes from the beginning while(head != null && head.val == val){ head = head.next; } // If list becomes empty if(head == null) return null; ListNode prev = head; ListNode curr = head.next; while(curr != null){ if(curr.val == val){ // Skip the node prev.next = curr.next; } else { // Move prev only when node is not removed prev = curr; } curr = curr.next; } return head; }}Why This WorksWe ensure prev always points to the last valid nodeWhen we find a node to delete:prev.next = curr.nextThis skips the unwanted nodeProblem With This Approach👉 Too many edge cases:Removing head nodesEmpty listAll nodes equalApproach 2: Dummy Node (Best & Clean Approach)IdeaWe create a fake node (dummy) before the head.dummy → head → rest of listThis helps us:👉 Treat head like a normal node👉 Avoid special casesVisualizationOriginal:1 → 2 → 6 → 3After dummy:-1 → 1 → 2 → 6 → 3Java Implementation (Best Approach)class Solution { public ListNode removeElements(ListNode head, int val) { // Step 1: Create dummy node ListNode dumm = new ListNode(-1, head); // Step 2: Start from dummy ListNode curr = dumm; while(curr.next != null){ // If next node needs to be removed if(curr.next.val == val){ // Skip that node curr.next = curr.next.next; } else { // Move forward only when no deletion curr = curr.next; } } // Step 3: Return new head return dumm.next; }}Step-by-Step Dry RunInput:1 → 2 → 6 → 3 → 4 → 5 → 6val = 6After dummy:-1 → 1 → 2 → 6 → 3 → 4 → 5 → 6Traversal:curr = -1 → 1 (keep)curr = 1 → 2 (keep)curr = 2 → 6 (remove)curr = 2 → 3 (keep)curr = 3 → 4 (keep)curr = 4 → 5 (keep)curr = 5 → 6 (remove)Final:1 → 2 → 3 → 4 → 5Time ComplexityO(n)We traverse the list once.Space ComplexityO(1)No extra space used.Why Dummy Node is PreferredWithout DummyWith DummyComplex edge casesClean logicSpecial handling for headNo special handlingError-proneSafe and readableApproach 3: Recursive Solution (Conceptual)IdeaWe process one node at a time and recursively solve for the rest.Codeclass Solution { public ListNode removeElements(ListNode head, int val) { if(head == null) return null; head.next = removeElements(head.next, val); if(head.val == val){ return head.next; } else { return head; } }}Time ComplexityO(n)Space ComplexityO(n)(due to recursion stack)Key TakeawaysLinked list problems are all about pointer manipulationAlways think about edge cases (especially head)Dummy node simplifies almost every linked list problemConclusionThe Remove Linked List Elements problem is perfect for understanding how linked lists work in real scenarios.While the manual approach works, the dummy node technique provides a much cleaner and safer solution.If you master this pattern, you will be able to solve many linked list problems easily in interviews.👉 Tip: Whenever you feel stuck in linked list problems, try adding a dummy node — it often simplifies everything!

Linked ListIterationDummy NodePointer ManipulationLeetCodeEasy

LeetCode 2: Add Two Numbers – Step-by-Step Linked List Addition Explained Clearly

Try the ProblemYou can practice the problem here:https://leetcode.com/problems/add-two-numbers/Problem Description (In Simple Words)You are given two linked lists, where:Each node contains a single digit (0–9)The digits are stored in reverse order👉 That means:[2,4,3] represents 342[5,6,4] represents 465Your task is:👉 Add these two numbers👉 Return the result as a linked list (also in reverse order)Important Points to UnderstandEach node contains only one digitNumbers are stored in reverse orderYou must return the answer as a linked listYou must handle carry just like normal additionExample WalkthroughExample 1Input:l1 = [2,4,3]l2 = [5,6,4]Interpretation:342 + 465 = 807Output:[7,0,8]Example 2Input:l1 = [0]l2 = [0]Output:[0]Example 3Input:l1 = [9,9,9,9,9,9,9]l2 = [9,9,9,9]Output:[8,9,9,9,0,0,0,1]Constraints1 <= number of nodes <= 1000 <= Node.val <= 9No leading zeros except the number 0Understanding the Core IdeaThis problem is essentially:👉 Adding two numbers digit by digitBut instead of arrays or integers, the digits are stored in linked lists.How Addition Works (Real-Life Analogy)Let’s add:342 + 465We normally add from right to left:2 + 5 = 74 + 6 = 10 → write 0, carry 13 + 4 + 1 = 8Now notice something important:👉 Linked list is already in reverse order👉 So we can directly process from left to rightThinking About the SolutionBefore coding, let’s think of possible approaches:Possible Ways to SolveConvert linked lists into numbers → add → convert back (Not safe due to overflow)Store digits in arrays and simulate additionTraverse both lists and simulate addition directly (best approach)Optimal Approach: Simulate Addition (Digit by Digit)Key IdeaWe traverse both linked lists and:Add corresponding digitsMaintain a carryCreate a new node for each digit of resultStep-by-Step LogicStep 1: InitializeCreate a dummy node (to simplify result building)Create a pointer curr to build the result listInitialize carry = 0Step 2: Traverse Both ListsContinue while:l1 != null OR l2 != nullAt each step:Start with carry:sum = carryAdd value from l1 (if exists)Add value from l2 (if exists)Step 3: Create New NodeDigit to store:sum % 10New carry:sum / 10Step 4: Move ForwardMove l1 and l2 if they existMove curr forwardStep 5: Handle Remaining CarryIf carry is not zero after loop:👉 Add one more nodeStep 6: Return ResultReturn:dummy.nextCode Implementation (With Explanation)class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { // Dummy node to simplify result construction ListNode dumm = new ListNode(-1); ListNode curr = dumm; int sum = 0; int carr = 0; // Traverse both lists while(l1 != null || l2 != null){ // Start with carry sum = carr; // Add l1 value if exists if(l1 != null){ sum += l1.val; l1 = l1.next; } // Add l2 value if exists if(l2 != null){ sum += l2.val; l2 = l2.next; } // Create new node with digit ListNode newNode = new ListNode(sum % 10); // Update carry carr = sum / 10; // Attach node curr.next = newNode; curr = curr.next; } // If carry remains if(carr != 0){ curr.next = new ListNode(carr); } return dumm.next; }}Dry Run (Important for Understanding)Input:l1 = [2,4,3]l2 = [5,6,4]Step-by-step:Step 1:2 + 5 = 7 → node(7), carry = 0Step 2:4 + 6 = 10 → node(0), carry = 1Step 3:3 + 4 + 1 = 8 → node(8), carry = 0Final:7 → 0 → 8Time ComplexityO(max(n, m))Where:n = length of l1m = length of l2Space ComplexityO(max(n, m))For storing the result linked list.Why Dummy Node is ImportantWithout dummy node:You need to handle first node separatelyWith dummy node:Code becomes clean and consistentNo special cases requiredCommon Mistakes to Avoid❌ Forgetting to handle carry❌ Not checking if l1 or l2 is null❌ Missing last carry node❌ Incorrect pointer movementKey TakeawaysThis is a simulation problemLinked list problems become easier with dummy nodesAlways think in terms of real-world analogy (addition)ConclusionThe Add Two Numbers problem is one of the most important linked list problems for interviews.It teaches:Pointer manipulationCarry handlingIterative traversalClean code using dummy nodesOnce you understand this pattern, many other linked list problems become much easier to solve.👉 Tip: Whenever you see problems involving numbers in linked lists, think of digit-by-digit simulation with carry.

Linked ListMathSimulationCarry HandlingDummy NodeLeetCode Medium

Remove Nth Node From End – The Smart Way to Solve in One Pass (LeetCode 19)

🚀 Try the ProblemPractice here:https://leetcode.com/problems/remove-nth-node-from-end-of-list/🤔 Let’s Think Differently…Imagine this list:1 → 2 → 3 → 4 → 5You are asked:👉 Remove the 2nd node from the endSo counting from end:5 (1st), 4 (2nd) ❌ remove thisFinal list:1 → 2 → 3 → 5🧠 Problem in Simple WordsYou are given:Head of a linked listA number n👉 Remove the nth node from the end👉 Return the updated list📦 Constraints1 <= number of nodes <= 300 <= Node.val <= 1001 <= n <= size of list🧩 First Thought (Counting Method)💡 IdeaCount total nodesFind position from start:position = total - nTraverse again and remove that node✅ Code (Counting Approach)class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { if(head == null) return head; // Step 1: Count nodes int co = 0; ListNode tempHead = head; while(tempHead != null){ co++; tempHead = tempHead.next; } // Step 2: If removing head if(co == n) return head.next; // Step 3: Find node before target int k = co - n; int con = 1; ListNode temp = head; while(con < k){ temp = temp.next; con++; } // Step 4: Remove node temp.next = temp.next.next; return head; }}⏱️ ComplexityTime ComplexityO(n) + O(n) = O(n)(two traversals)Space ComplexityO(1)⚠️ Limitation of This Approach👉 It requires two passesBut the problem asks:Can you solve it in one pass?🚀 Optimal Approach: Two Pointer Technique (One Pass)Now comes the interesting part 🔥🧠 Core IdeaWe use two pointers:fast pointerslow pointer🎯 Trick👉 Move fast pointer n steps aheadThen move both pointers together until:fast reaches endAt that moment:👉 slow will be at the node before the one to remove📌 Why This WorksBecause the gap between fast and slow is always n nodesSo when fast reaches end:👉 slow is exactly where we need it🔥 Step-by-Step VisualizationList:1 → 2 → 3 → 4 → 5n = 2Step 1: Move fast 2 stepsfast → 3slow → 1Step 2: Move both togetherfast → 4, slow → 2fast → 5, slow → 3fast → null, slow → 4👉 Now slow is at node before target🧼 Clean and Safe Approach (Using Dummy Node)Using dummy node avoids edge cases like removing head.💻 Code (Optimal One Pass Solution)class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { // Dummy node to handle edge cases ListNode dummy = new ListNode(0, head); ListNode fast = dummy; ListNode slow = dummy; // Move fast pointer n steps ahead for(int i = 0; i < n; i++){ fast = fast.next; } // Move both pointers while(fast.next != null){ fast = fast.next; slow = slow.next; } // Remove nth node slow.next = slow.next.next; return dummy.next; }}⏱️ ComplexityTime ComplexityO(n)(single pass)Space ComplexityO(1)⚖️ Comparing ApproachesApproachPassesTimeSpaceDifficultyCounting2O(n)O(1)EasyTwo Pointer1O(n)O(1)Optimal❌ Common MistakesForgetting to handle removing head nodeNot using dummy nodeOff-by-one errors in pointer movementMoving fast incorrectly🔥 Interview InsightThis problem is a classic example of:Fast & Slow Pointer TechniqueUsed in many problems like:Cycle DetectionMiddle of Linked ListPalindrome Linked List🧠 Final ThoughtAt first, counting feels natural…But once you learn this trick:"Create a gap and move together"👉 You unlock a powerful pattern.🚀 ConclusionThe Remove Nth Node From End problem is not just about deletion…It teaches:Efficient traversalPointer coordinationOne-pass optimization👉 Tip: Whenever you see “from end”, think:"Can I use two pointers with a gap?"That’s your shortcut to solving these problems like a pro 🚀

Linked ListTwo PointersFast & Slow PointerOne Pass AlgorithmLeetCodeMedium

Master LeetCode 92: Reverse Linked List II | Detailed Java Solution & Explanation

If you are preparing for software engineering interviews, you already know that Linked Lists are a favourite topic among interviewers. While reversing an entire linked list is a standard beginner problem, reversing only a specific section of it requires a bit more pointer magic.In this blog post, we will tackle LeetCode 92. Reverse Linked List II. We will break down the problem in plain English, walk through a highly intuitive modular approach, and then look at an optimized one-pass technique.Let’s dive in!Understanding the ProblemQuestion Statement:Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.Example:Input: head = [1,2,3,4,5], left = 2, right = 4Output: [1,4,3,2,5]In Simple Words:Imagine a chain of connected boxes. You don't want to flip the whole chain backwards. You only want to flip a specific middle section (from the 2nd box to the 4th box), while keeping the first and last boxes exactly where they are.Approach 1: The Intuitive Modular Approach (Find, Reverse, Connect)When solving complex linked list problems, breaking the problem into smaller helper functions is an excellent software engineering practice.In this approach, we will:Use a Dummy Node. This is a lifesaver when left = 1 (meaning we have to reverse from the very first node).Traverse the list to find the exact boundaries: the node just before the reversal (slow), the start of the reversal (leftNode), and the end of the reversal (rightNode).Pass the sub-list to a helper function that reverses it.Reconnect the newly reversed sub-list back to the main list.Here is the Java code for this approach:/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution { // Helper function to reverse a portion of the list public ListNode reverse(ListNode LeftHead, ListNode rightHead){ ListNode curr = LeftHead; ListNode prev = rightHead; // Standard linked list reversal logic while(curr != rightHead){ ListNode newnode = curr.next; curr.next = prev; prev = curr; curr = newnode; } return prev; } public ListNode reverseBetween(ListNode head, int left, int right) { if(left == 1 && right == 1) return head; // Dummy node helps handle edge cases easily ListNode dummy = new ListNode(-1); dummy.next = head; ListNode leftNode = null; ListNode rightNode = null; ListNode curr = head; int leftC = 1; int rightC = 1; ListNode slow = dummy; // Traverse to find the exact bounds of our sublist while(curr != null){ if(leftC == left - 1){ slow = curr; // 'slow' is the node just before the reversed section } if(leftC == left){ leftNode = curr; } if(rightC == right){ rightNode = curr; } if(leftC == left && rightC == right){ break; // We found both bounds, no need to traverse further } leftC++; rightC++; curr = curr.next; } // Reverse the sublist and connect it back ListNode rev = reverse(leftNode, rightNode.next); slow.next = rev; return dummy.next; }}🔍 Dry Run of Approach 1Let’s trace head = [1, 2, 3, 4, 5], left = 2, right = 4.Step 1: Initializationdummy = -1 -> 1 -> 2 -> 3 -> 4 -> 5slow = -1 (dummy node)Step 2: Finding Bounds (While Loop)We move curr through the list.When curr is at 1 (Position 1): left - 1 is 1, so slow becomes node 1.When curr is at 2 (Position 2): leftNode becomes node 2.When curr is at 4 (Position 4): rightNode becomes node 4. We break the loop.Step 3: The Helper ReversalWe call reverse(leftNode, rightNode.next), which means reverse(Node 2, Node 5).Inside the helper, we reverse the links for 2, 3, and 4.Because we initialized prev as rightHead (Node 5), Node 2's next becomes Node 5.The helper returns Node 4 as the new head of this reversed chunk. The chunk now looks like: 4 -> 3 -> 2 -> 5.Step 4: ReconnectionBack in the main function, slow (Node 1) is connected to the returned reversed list: slow.next = rev.Final List: dummy -> 1 -> 4 -> 3 -> 2 -> 5.Return dummy.next!Time & Space Complexity:Time Complexity: O(N). We traverse the list to find the pointers, and then the helper traverses the sub-list to reverse it. Since we visit nodes a maximum of two times, it is linear time.Space Complexity: O(1). We are only creating a few pointers (dummy, slow, curr, etc.), requiring no extra dynamic memory.Approach 2: The Optimized One-Pass SolutionLeetCode includes a follow-up challenge: "Could you do it in one pass?"While the first approach is incredibly readable, we can optimize it to reverse the nodes as we traverse them, eliminating the need for a separate helper function or a second sub-list traversal.In this approach, we:Move a prev pointer to the node just before left.Keep a curr pointer at left.Use a for loop to extract the node immediately after curr and move it to the front of the reversed sub-list. We do this exactly right - left times.class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { if (head == null || left == right) return head; ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; // Step 1: Reach the node just before 'left' for (int i = 0; i < left - 1; i++) { prev = prev.next; } // Step 2: Start the reversal process ListNode curr = prev.next; for (int i = 0; i < right - left; i++) { ListNode nextNode = curr.next; // Node to be moved to the front curr.next = nextNode.next; // Detach nextNode nextNode.next = prev.next; // Point nextNode to the current front of sublist prev.next = nextNode; // Make nextNode the new front of the sublist } return dummy.next; }}🔍 Why this works (The Pointer Magic)If we are reversing [1, 2, 3, 4, 5] from 2 to 4:prev is at 1. curr is at 2.Iteration 1: Grab 3, put it after 1. List: [1, 3, 2, 4, 5].Iteration 2: Grab 4, put it after 1. List: [1, 4, 3, 2, 5].Done! We achieved the reversal in a strict single pass.Time & Space Complexity:Time Complexity: O(N). We touch each node exactly once.Space Complexity: O(1). Done entirely in-place.ConclusionReversing a portion of a linked list is a fantastic way to test your understanding of pointer manipulation.Approach 1 is amazing for interviews because it shows you can modularize code and break big problems into smaller, testable functions.Approach 2 is the perfect "flex" to show the interviewer that you understand optimization and single-pass algorithms.I highly recommend writing down the dry run on a piece of paper and drawing arrows to see how the pointers shift. That is the secret to mastering Linked Lists!Happy Coding! 💻🚀

LeetCodeLinkedListJavaReverse LinkedList II