Search Blogs

Showing results for "In-Place Algorithm"

Found 7 results

LeetCode 328: Odd Even Linked List – Clean and Easy Explanation with Multiple Approaches

Try the ProblemYou can practice the problem here:https://leetcode.com/problems/odd-even-linked-list/Problem Description (In Very Simple Words)You are given the head of a linked list.Your task is:👉 Rearrange the list such that:All nodes at odd positions come firstFollowed by all nodes at even positionsImportant Clarification❗ This problem is about positions (indices), NOT values.1st node → Odd2nd node → Even3rd node → Odd4th node → EvenExample WalkthroughExample 1Input:[1,2,3,4,5]Positions:1(odd), 2(even), 3(odd), 4(even), 5(odd)Output:[1,3,5,2,4]Example 2Input:[2,1,3,5,6,4,7]Output:[2,3,6,7,1,5,4]Constraints0 <= number of nodes <= 10^4-10^6 <= Node.val <= 10^6Core Idea of the ProblemWe need to:Separate nodes into two groups:Odd index nodesEven index nodesMaintain their original orderFinally:👉 Attach even list after odd listThinking About Different ApproachesWhen solving this problem, multiple approaches may come to mind:Approach 1: Create New ListsIdeaTraverse the listCreate new nodes for odd and even positionsBuild two separate listsMerge themProblem with This Approach❌ Uses extra space❌ Not optimal (violates O(1) space requirement)❌ Code becomes messy and harder to maintainYour approach is logically correct, but:👉 It is not optimal and can be simplified a lot.Approach 2: Brute Force Using Array/ListIdeaStore nodes in an arrayRearrange based on indicesRebuild linked listComplexityTime: O(n)Space: O(n) ❌ (Not allowed)Approach 3: Optimal In-Place Approach (Best Solution)This is the cleanest and most important approach.Optimal Approach: Two Pointer Technique (In-Place)IdeaInstead of creating new nodes:👉 We rearrange the existing nodesWe maintain:odd → points to odd nodeseven → points to even nodesevenHead → stores start of even listVisualizationInput:1 → 2 → 3 → 4 → 5We separate into:Odd: 1 → 3 → 5Even: 2 → 4Final:1 → 3 → 5 → 2 → 4Step-by-Step LogicStep 1: Initialize pointersodd = headeven = head.nextevenHead = head.nextStep 2: Traverse the listWhile:even != null && even.next != nullUpdate:odd.next = odd.next.nexteven.next = even.next.nextMove pointers forward:odd = odd.nexteven = even.nextStep 3: Mergeodd.next = evenHeadClean Java Implementation (Optimal)class Solution { public ListNode oddEvenList(ListNode head) { // Edge case if(head == null || head.next == null) return head; // Initialize pointers ListNode odd = head; ListNode even = head.next; ListNode evenHead = even; // Rearranging nodes while(even != null && even.next != null){ odd.next = odd.next.next; // Link next odd even.next = even.next.next; // Link next even odd = odd.next; even = even.next; } // Attach even list after odd list odd.next = evenHead; return head; }}Dry Run (Important)Input:1 → 2 → 3 → 4 → 5Steps:Iteration 1:odd → 1, even → 2Link:1 → 32 → 4Iteration 2:odd → 3, even → 4Link:3 → 54 → nullFinal connection:5 → 2Result:1 → 3 → 5 → 2 → 4Time ComplexityO(n)We traverse the list once.Space ComplexityO(1)No extra space used.Why This Approach is BestFeatureResultExtra Space❌ NoneClean Code✅ YesEfficient✅ O(n)Interview Friendly✅ HighlyCommon Mistakes❌ Confusing values with positions❌ Creating new nodes unnecessarily❌ Forgetting to connect even list at the end❌ Breaking the list accidentallyKey LearningThis problem teaches:In-place linked list manipulationPointer handlingList partitioningFinal ThoughtsThe Odd Even Linked List problem is a classic example of how powerful pointer manipulation can be.Even though creating new nodes might seem easier at first, the in-place approach is:👉 Faster👉 Cleaner👉 Interview optimized👉 Tip: Whenever you are asked to rearrange a linked list, always think:"Can I solve this by just changing pointers instead of creating new nodes?"That’s the key to mastering linked list problems 🚀

Linked ListPointer ManipulationIn-Place AlgorithmTwo PointersLeetCode Medium

Quick Sort Algorithm Explained | Java Implementation, Partition Logic & Complexity

IntroductionQuick Sort is one of the most powerful and widely used sorting algorithms in computer science. It follows the Divide and Conquer approach and is known for its excellent average-case performance.What makes Quick Sort special is:It sorts in-place (no extra array required)It is faster in practice than many O(n log n) algorithms like Merge SortIt is heavily used in real-world systems and librariesIn this article, we’ll go deep into:Intuition behind Quick SortPartition logic (most important part)Step-by-step dry runJava implementation with commentsTime complexity analysisCommon mistakes and optimizations🔗 Problem LinkGeeksforGeeks: Quick SortProblem StatementGiven an array arr[], sort it in ascending order using Quick Sort.Requirements:Use Divide and ConquerChoose pivot elementPlace pivot in correct positionElements smaller → left sideElements greater → right sideExamplesExample 1Input:arr = [4, 1, 3, 9, 7]Output:[1, 3, 4, 7, 9]Example 2Input:arr = [2, 1, 6, 10, 4, 1, 3, 9, 7]Output:[1, 1, 2, 3, 4, 6, 7, 9, 10]Core Idea of Quick SortPick a pivot → Place it correctly → Recursively sort left & right🔥 Key Insight (Partition is Everything)Quick Sort depends entirely on partitioning:👉 After partition:Pivot is at its correct sorted positionLeft side → smaller elementsRight side → larger elementsIntuition (Visual Understanding)Consider:[4, 1, 3, 9, 7]Step 1: Choose PivotLet’s say pivot = 4Step 2: Rearrange Elements[1, 3] 4 [9, 7]Now:Left → smallerRight → largerStep 3: Apply RecursivelyLeft: [1, 3]Right: [9, 7]Final result:[1, 3, 4, 7, 9]Partition Logic (Most Important)Your implementation uses:Pivot = first elementTwo pointers:i → moves forwardj → moves backwardJava Codeclass Solution { public void quickSort(int[] arr, int low, int high) { // Base case: if array has 1 or 0 elements if (low < high) { // Partition array and get pivot index int pivotInd = partition(arr, low, high); // Sort left part quickSort(arr, low, pivotInd - 1); // Sort right part quickSort(arr, pivotInd + 1, high); } } // Function to swap two elements void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } private int partition(int[] arr, int low, int high) { int pivot = arr[low]; // choosing first element as pivot int i = low + 1; // start from next element int j = high; // start from end while (i <= j) { // Move i forward until element > pivot while (i <= high && arr[i] <= pivot) { i++; } // Move j backward until element <= pivot while (j >= low && arr[j] > pivot) { j--; } // Swap if pointers haven't crossed if (i < j) { swap(arr, i, j); } } // Place pivot at correct position swap(arr, low, j); return j; // return pivot index }}Step-by-Step Dry RunInput:[4, 1, 3, 9, 7]Execution:Pivot = 4i → moves until element > 4j → moves until element ≤ 4Swaps happen → pivot placed correctlyFinal partition:[1, 3, 4, 9, 7]Complexity AnalysisTime ComplexityCaseComplexityBest CaseO(n log n)Average CaseO(n log n)Worst CaseO(n²)Why Worst Case Happens?When array is:Already sortedReverse sortedPivot always becomes smallest/largest.Space ComplexityO(log n) (recursion stack)❌ Common MistakesWrong partition logicInfinite loops in while conditionsIncorrect pivot placementNot handling duplicates properly⚡ Optimizations1. Random PivotAvoid worst-case:int pivotIndex = low + new Random().nextInt(high - low + 1);swap(arr, low, pivotIndex);2. Median of ThreeChoose better pivot:median(arr[low], arr[mid], arr[high])Quick Sort vs Merge SortFeatureQuick SortMerge Sort link to get moreSpaceO(log n)O(n)SpeedFaster (practical)StableWorst CaseO(n²)O(n log n)Why Quick Sort is PreferredCache-friendlyIn-place sortingFaster in real-world scenariosKey TakeawaysPartition is the heart of Quick SortPivot must be placed correctlyRecursion splits problem efficientlyAvoid worst case using random pivotWhen to Use Quick SortLarge arraysMemory constraints (in-place)Performance-critical applicationsConclusionQuick Sort is one of the most efficient and practical sorting algorithms. Mastering its partition logic is crucial for solving advanced problems and performing well in coding interviews.Understanding how pointers move and how pivot is placed will make this algorithm intuitive and powerful.Frequently Asked Questions (FAQs)1. Is Quick Sort stable?No, it is not stable.2. Why is Quick Sort faster than Merge Sort?Because it avoids extra space and is cache-efficient.3. What is the most important part?👉 Partition logic

MediumJavaSortingQuick SortGeeksofGeeks

LeetCode 36: Valid Sudoku Explained – Java Solutions, Intuition & Formula Dry Run

IntroductionSudoku is a universally beloved puzzle, but validating a Sudoku boardalgorithmically is a classic technical interview question. In this post, we aregoing to dive deep into LeetCode 36: Valid Sudoku.We won't just look at the code; we will explore the intuition behind the problemso you don't have to memorize anything. We’ll cover an ingenious in-placevalidation approach, break down the complex math formula used to check3 \times 3 sub-boxes, and look at an alternative optimal solution usingHashSets.Let's dive in!Understanding the ProblemThe problem asks us to determine if a partially filled 9 \times 9 Sudoku boardis valid. To be valid, the filled cells must follow three straightforward rules:1. Each row must contain the digits 1-9 without repetition.2. Each column must contain the digits 1-9 without repetition.3. Each of the nine 3 \times 3 sub-boxes must contain the digits 1-9 withoutrepetition.Important Note: A valid board doesn't mean the board is fully solvable! We onlycare about checking the numbers that are currently on the board.Intuition: How to Think About the ProblemBefore writing code, how do we, as humans, check if a Sudoku board is valid? Ifyou place a 5 in a cell, you quickly scan horizontally (its row), vertically(its column), and within its small 3 \times 3 square. If you see another 5, theboard is invalid.To translate this to code, we have two choices:1. The Simulation Approach: Go cell by cell. Pick up the number, hide it, andcheck its row, column, and 3 \times 3 box to see if that number existsanywhere else. (This is the approach we will look at first).2. The Memory Approach: Go cell by cell, but keep a "notebook" (like a HashTable) of everything we have seen so far. If we see a number we've alreadywritten down for a specific row, column, or box, it's invalid.Approach 1: The In-Place Validation (Space-Optimized)Here is a brilliant solution that validates the board without using any extradata structures.The Logic: Iterate through every cell on the board. When we find a number, wetemporarily replace it with a . (empty space). Then, we iterate 9 times to checkits entire row, column, and sub-box. If the number is found, we return false.Otherwise, we put the number back and move to the next cell.The Java Codeclass Solution {public boolean isvalid(char[][] board, int i, int j, char k) {for(int m = 0; m < 9; m++) {// Check rowif(board[i][m] == k) return false;// Check columnif(board[m][j] == k) return false;// Check 3x3 sub-boxif(board[3 * (i / 3) + m / 3][3 * (j / 3) + m % 3] == k) return false;}return true;}public boolean isValidSudoku(char[][] board) {for(int i = 0; i < board.length; i++) {for(int j = 0; j < board[0].length; j++) {if(board[i][j] != '.') {char temp = board[i][j];board[i][j] = '.'; // Temporarily remove the numberif(!isvalid(board, i, j, temp)) {return false;}board[i][j] = temp; // Put the number back}}}return true;}}The Math Breakdown: Demystifying the 3 \times 3 Grid FormulaThe hardest part of this code to understand is this exact line: board[3*(i/3) +m/3][3*(j/3) + m%3]How does a single loop variable m (from 0 to 8) traverse a 3 \times 3 grid?Let’s do a dry run.Step 1: Finding the Starting Point of the BoxThe grid is 9 \times 9, broken into nine 3 \times 3 boxes. If we are at a randomcell, say row i = 4, col j = 5, which box are we in? Because integer division inJava drops the decimal:i / 3 = 4 / 3 = 1j / 3 = 5 / 3 = 1Now multiply by 3 to get the actual starting coordinates (top-left corner) ofthat specific sub-box:3 * 1 = 3 (Row offset)3 * 1 = 3 (Col offset) So, the 3 \times 3 box starts at row 3, col 3.Step 2: Traversing the Box (Dry Run)Now, as m goes from 0 to 8, we use m / 3 for rows and m % 3 for columns:m = 0: row offset 0/3 = 0, col offset 0%3 = 0 \rightarrow Checks (3+0, 3+0) = (3, 3)m = 1: row offset 1/3 = 0, col offset 1%3 = 1 \rightarrow Checks (3+0, 3+1) = (3, 4)m = 2: row offset 2/3 = 0, col offset 2%3 = 2 \rightarrow Checks (3+0, 3+2) = (3, 5)m = 3: row offset 3/3 = 1, col offset 3%3 = 0 \rightarrow Checks (3+1, 3+0) = (4, 3)m = 4: row offset 4/3 = 1, col offset 4%3 = 1 \rightarrow Checks (3+1, 3+1) = (4, 4)...and so on up to m = 8.This brilliant math formula maps a 1D loop (0 to 8) directly onto a 2D3 \times 3 grid perfectly! No nested loops needed inside the isvalid function.Approach 2: The HashSet Solution (Single Pass)While the first approach is highly space-efficient, it does a bit of redundantchecking. An alternative approach that interviewers love is using a HashSet.Instead of checking rows and columns every time we see a number, we generate aunique "string signature" for every number and attempt to add it to a HashSet.If we see a 5 at row 0 and col 1, we create three strings:1. "5 in row 0"2. "5 in col 1"3. "5 in block 0-0"The HashSet.add() method returns false if the item already exists in the set. Ifit returns false, we instantly know the board is invalid!HashSet Java Code:class Solution {public boolean isValidSudoku(char[][] board) {HashSet<String> seen = new HashSet<>();for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {char number = board[i][j];if (number != '.') {// HashSet.add() returns false if the element already existsif (!seen.add(number + " in row " + i) ||!seen.add(number + " in col " + j) ||!seen.add(number + " in block " + i/3 + "-" + j/3)) {return false;}}}}return true;}}Notice how we use i/3 + "-" + j/3 to identify the blocks. Top-left is block 0-0,bottom-right is block 2-2.Time and Space Complexity BreakdownInterviewers will always ask for your complexity analysis. Because a Sudokuboard is strictly fixed at 9 \times 9, the strict Big-O is actually constant.However, let's look at it conceptually as if the board were N \times N.Approach 1: In-Place Validation (Your Solution)Time Complexity: O(1) (Strictly speaking). We traverse 81 cells, and foreach cell, we do at most 9 iterations. 81 \times 9 = 729 operations. Since729 is a constant, it's O(1). (If the board was N \times N, time complexitywould be O(N^3) because for N^2 cells, we iterate N times).Space Complexity: O(1). We only use primitive variables (i, j, k, m, temp).No extra memory is allocated.Approach 2: HashSet ApproachTime Complexity: O(1). We traverse the 81 cells exactly once. Generatingstrings and adding to a HashSet takes O(1) time. (If the board wasN \times N, time complexity would be O(N^2)).Space Complexity: O(1). The HashSet will store a maximum of81 \times 3 = 243 strings. Since this upper limit is fixed, space isconstant.ConclusionThe Valid Sudoku problem is a fantastic exercise in matrix traversal andcoordinate math.When solving this in an interview:1. Use the first approach if you want to impress the interviewer with O(1)space complexity and your deep understanding of math formulas (the /3 and %3trick).2. Use the second approach (HashSet) if you want to show off your knowledge ofdata structures and write highly readable, clean, and clever code.I hope this breakdown gives you the intuition needed so you never have tomemorize the code for LeetCode 36!Happy Coding! Keep Learning🤟

LeetCodeJavaMatrixHash TableRecursionBacktrackingMedium

Sort Colors

LeetCode Problem 75 Link of the Problem to try -: LinkProblem Statement :- Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.Example 1:Input: nums = [2,0,2,1,1,0]Output: [0,0,1,1,2,2]Example 2:Input: nums = [2,0,1]Output: [0,1,2]You must solve this problem without using the library's sort function.My Approach (1)I have solved this question via my approach by counting frequency of each element like 0,1 and 2 as I avoid to use nested loops but i used for loops multiple times but as loops are used in a constant space of time that's why they did not increases the time complexity that's why my solution time complexity is O(n) even though I need to traverse array multiple time.Here is the Approach:int zeroCounter= 0;int oneCounter = 0;int twoCounter=0;int counter =0;for(int i =0; i< nums.length; i++){if(nums[i] == 0){zeroCounter++;}else if(nums[i] == 1){oneCounter++;}else{twoCounter++;}}for(int i=0; i<zeroCounter;i++){nums[i] = 0;counter++;}for(int i=0; i<oneCounter;i++){nums[counter] = 1;counter++;}for(int i=0; i<twoCounter;i++){nums[counter] = 2;counter++;}My Approach (2)This approach uses a algorithm called DNF (Dutch National Flag) Algorithm in this algorithm we have to focus on two elements out of three and make sure those two element are on the correct place as the last one came automatically to the correct position even though my approach(1) is uses loops multiple time but this approach is also take O(n) time complexity but uses loop one time that's why this approach is far cleaner than approach (1).int low =0;int high= nums.length-1;int curr =0;while(curr <= high){if(nums[curr] == 0){int temp = nums[low];nums[low] = nums[curr];nums[curr] = temp;low++;curr++;}else if( nums[curr] == 1){curr++;}else{int temp = nums[curr];nums[curr] = nums[high];nums[high] = temp;high--;}}

LeetCodeMediumTwo PointerDutchman Flag Algorithm

Merge Sort Algorithm Explained | Java Implementation, Intuition & Complexity

IntroductionSorting is one of the most fundamental operations in computer science, and Merge Sort is among the most efficient and widely used sorting algorithms.It follows the Divide and Conquer approach, making it highly scalable and predictable even for large datasets.In this article, we will cover:Intuition behind Merge SortStep-by-step breakdownMultiple approachesJava implementation with commentsTime & space complexity analysis🔗 Problem LinkGeeksforGeeks: Merge SortProblem StatementGiven an array arr[] with starting index l and ending index r, sort the array using the Merge Sort algorithm.ExamplesExample 1Input:arr = [4, 1, 3, 9, 7]Output:[1, 3, 4, 7, 9]Example 2Input:arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]Output:[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]Key InsightMerge Sort works by:Divide → Conquer → CombineDivide the array into two halvesRecursively sort each halfMerge both sorted halvesIntuition (Visual Understanding)For:[4, 1, 3, 9, 7]Step 1: Divide[4, 1, 3] [9, 7][4, 1] [3] [9] [7][4] [1]Step 2: Merge[4] [1] → [1, 4][1, 4] [3] → [1, 3, 4][9] [7] → [7, 9]Step 3: Final Merge[1, 3, 4] + [7, 9] → [1, 3, 4, 7, 9]Approach 1: Recursive Merge Sort (Top-Down)IdeaKeep dividing until single elements remainMerge sorted subarraysJava Codeclass Solution { // Function to merge two sorted halves void merge(int[] arr, int l, int mid, int h) { // Temporary array to store merged result int[] temp = new int[h - l + 1]; int i = l; // pointer for left half int j = mid + 1; // pointer for right half int k = 0; // pointer for temp array // Compare elements from both halves while (i <= mid && j <= h) { if (arr[i] <= arr[j]) { temp[k] = arr[i]; i++; } else { temp[k] = arr[j]; j++; } k++; } // Copy remaining elements from left half while (i <= mid) { temp[k] = arr[i]; i++; k++; } // Copy remaining elements from right half while (j <= h) { temp[k] = arr[j]; j++; k++; } // Copy sorted elements back to original array for (int m = 0; m < temp.length; m++) { arr[l + m] = temp[m]; } } // Recursive merge sort function void mergeSort(int arr[], int l, int h) { // Base case: single element if (l >= h) return; int mid = l + (h - l) / 2; // Sort left half mergeSort(arr, l, mid); // Sort right half mergeSort(arr, mid + 1, h); // Merge both halves merge(arr, l, mid, h); }}Approach 2: Iterative Merge Sort (Bottom-Up)IdeaStart with subarrays of size 1Merge pairsIncrease size graduallyCodeclass Solution { void merge(int[] arr, int l, int mid, int h) { int[] temp = new int[h - l + 1]; int i = l, j = mid + 1, k = 0; while (i <= mid && j <= h) { if (arr[i] <= arr[j]) temp[k++] = arr[i++]; else temp[k++] = arr[j++]; } while (i <= mid) temp[k++] = arr[i++]; while (j <= h) temp[k++] = arr[j++]; for (int m = 0; m < temp.length; m++) { arr[l + m] = temp[m]; } } void mergeSort(int[] arr, int n) { for (int size = 1; size < n; size *= 2) { for (int l = 0; l < n - size; l += 2 * size) { int mid = l + size - 1; int h = Math.min(l + 2 * size - 1, n - 1); merge(arr, l, mid, h); } } }}Approach 3: Using Built-in Sorting (For Comparison)Arrays.sort(arr);👉 Internally uses optimized algorithms (TimSort in Java)Complexity AnalysisTime ComplexityCaseComplexityBestO(n log n)AverageO(n log n)WorstO(n log n)Space ComplexityO(n) (extra array for merging)Why Merge Sort is PowerfulStable sorting algorithmWorks efficiently on large datasetsPredictable performanceUsed in external sorting (large files)❌ Why Not Use Bubble/Selection Sort?AlgorithmTime ComplexityBubble SortO(n²)Selection SortO(n²)Merge SortO(n log n) ✅Key TakeawaysMerge Sort uses divide and conquerRecursion splits problem into smaller partsMerging is the key stepAlways O(n log n), regardless of inputWhen to Use Merge SortLarge datasetsLinked lists (very efficient)Stable sorting requiredExternal sortingConclusionMerge Sort is one of the most reliable and efficient sorting algorithms. Understanding its recursive structure and merging process is essential for mastering advanced algorithms.Once you grasp the divide-and-conquer pattern, it becomes easier to solve many complex problems.Frequently Asked Questions (FAQs)1. Is Merge Sort stable?Yes, it maintains the relative order of equal elements.2. Why is extra space required?Because we use a temporary array during merging.3. Can it be done in-place?Not efficiently; standard merge sort requires extra space.

GeekfOfGeeksMediumSortingMerge SortJava

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

LeetCode 143 Reorder List - Java Solution Explained

IntroductionLeetCode 143 Reorder List is one of those problems that looks simple when you read it but immediately makes you wonder — where do I even start? There is no single trick that solves it. Instead it combines three separate linked list techniques into one clean solution. Mastering this problem means you have genuinely understood linked lists at an intermediate level.You can find the problem here — LeetCode 143 Reorder List.This article walks through everything — what the problem wants, the intuition behind each step, all three techniques used, a detailed dry run, complexity analysis, and common mistakes beginners make.What Is the Problem Really Asking?You have a linked list: L0 → L1 → L2 → ... → LnYou need to reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ...In plain English — take one node from the front, then one from the back, then one from the front, then one from the back, and keep alternating until all nodes are used.Example:Input: 1 → 2 → 3 → 4 → 5Output: 1 → 5 → 2 → 4 → 3Node 1 from front, Node 5 from back, Node 2 from front, Node 4 from back, Node 3 stays in middle.Real Life Analogy — Dealing Cards From Both EndsImagine you have a deck of cards laid out in a line face up: 1, 2, 3, 4, 5. Now you deal them by alternately picking from the left end and the right end of the line:Pick 1 from left → placePick 5 from right → place after 1Pick 2 from left → place after 5Pick 4 from right → place after 2Pick 3 (only one left) → place after 4Result: 1, 5, 2, 4, 3That is exactly what the problem wants. The challenge is doing this efficiently on a singly linked list where you cannot just index from the back.Why This Problem Is Hard for BeginnersIn an array you can just use two pointers — one at the start and one at the end — and swap/interleave easily. But a singly linked list only goes forward. You cannot go backwards. You cannot easily access the last element.This is why the problem requires a three-step approach that cleverly works around the limitations of a singly linked list.The Three Step ApproachEvery experienced developer solves this problem in exactly three steps:Step 1 — Find the middle of the linked list using the Fast & Slow Pointer techniqueStep 2 — Reverse the second half of the linked listStep 3 — Merge the two halves by alternating nodes from eachLet us understand each step deeply before looking at code.Step 1: Finding the Middle — Fast & Slow PointerThe Fast & Slow Pointer technique (also called Floyd's algorithm) uses two pointers moving at different speeds through the list:slow moves one step at a timefast moves two steps at a timeWhen fast reaches the end, slow is exactly at the middle. This works because fast covers twice the distance of slow in the same number of steps.ListNode fast = head;ListNode slow = head;while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next;}// slow is now at the middleFor 1 → 2 → 3 → 4 → 5:Start: slow=1, fast=1Step 1: slow=2, fast=3Step 2: slow=3, fast=5 (fast.next is null, stop)Middle is node 3For 1 → 2 → 3 → 4:Start: slow=1, fast=1Step 1: slow=2, fast=3Step 2: fast.next.next is null, stopslow=2, middle is node 2After finding the middle, we cut the list in two by setting slow.next = null. This disconnects the first half from the second half.Step 2: Reversing the Second HalfOnce we have the second half starting from slow.next, we reverse it. After reversal, what was the last node becomes the first — giving us easy access to the back elements of the original list.public ListNode reverse(ListNode head) { ListNode curr = head; ListNode prev = null; while (curr != null) { ListNode next = curr.next; // save next curr.next = prev; // reverse the link prev = curr; // move prev forward curr = next; // move curr forward } return prev; // prev is the new head}For second half 3 → 4 → 5 (from the first example):Reverse → 5 → 4 → 3Now we have:First half: 1 → 2 → 3 (but 3 is the end since we cut at slow)Wait — actually after cutting at slow=3: first half is 1 → 2 → 3, second half reversed is 5 → 4Let us be precise. For 1 → 2 → 3 → 4 → 5, slow stops at 3. slow.next = null cuts to give:First half: 1 → 2 → 3 → nullSecond half before reverse: 4 → 5Second half after reverse: 5 → 4Step 3: Merging Two HalvesNow we have two lists and we merge them by alternately taking one node from each:Take from first half, take from second half, take from first half, take from second half...ListNode orig = head; // pointer for first halfListNode newhead = second; // pointer for reversed second halfwhile (newhead != null) { ListNode temp1 = orig.next; // save next of first half ListNode temp2 = newhead.next; // save next of second half orig.next = newhead; // first → second newhead.next = temp1; // second → next of first orig = temp1; // advance first half pointer newhead = temp2; // advance second half pointer}Why do we loop on newhead != null and not orig != null? Because the second half is always equal to or shorter than the first half (we cut at middle). Once the second half is exhausted, the remaining first half nodes are already in the correct position.Complete Solutionclass Solution { public ListNode reverse(ListNode head) { ListNode curr = head; ListNode prev = null; while (curr != null) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } public void reorderList(ListNode head) { // Step 1: Find middle using fast & slow pointer ListNode fast = head; ListNode slow = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } // Step 2: Reverse second half ListNode newhead = reverse(slow.next); slow.next = null; // cut the list into two halves // Step 3: Merge two halves alternately ListNode orig = head; while (newhead != null) { ListNode temp1 = orig.next; ListNode temp2 = newhead.next; orig.next = newhead; newhead.next = temp1; orig = temp1; newhead = temp2; } }}Complete Dry Run — head = [1, 2, 3, 4, 5]Step 1: Find MiddleList: 1 → 2 → 3 → 4 → 5Initial: slow=1, fast=1Iteration 1: slow=2, fast=3Iteration 2: fast.next=4, fast.next.next=5 → slow=3, fast=5fast.next is null → stopslow is at node 3Step 2: Cut and ReverseCut: slow.next = nullFirst half: 1 → 2 → 3 → nullSecond half: 4 → 5Reverse second half 4 → 5:prev=null, curr=4 → next=5, 4.next=null, prev=4, curr=5prev=4, curr=5 → next=null, 5.next=4, prev=5, curr=nullReturn prev=5Reversed second half: 5 → 4 → nullStep 3: Mergeorig=1, newhead=5Iteration 1:temp1 = orig.next = 2temp2 = newhead.next = 4orig.next = newhead → 1.next = 5newhead.next = temp1 → 5.next = 2orig = temp1 = 2newhead = temp2 = 4List so far: 1 → 5 → 2 → 3Iteration 2:temp1 = orig.next = 3temp2 = newhead.next = nullorig.next = newhead → 2.next = 4newhead.next = temp1 → 4.next = 3orig = temp1 = 3newhead = temp2 = nullList so far: 1 → 5 → 2 → 4 → 3newhead is null → loop endsFinal result: 1 → 5 → 2 → 4 → 3 ✅Dry Run — head = [1, 2, 3, 4]Step 1: Find MiddleInitial: slow=1, fast=1Iteration 1: slow=2, fast=3fast.next=4, fast.next.next=null → stopslow is at node 2Step 2: Cut and ReverseFirst half: 1 → 2 → nullSecond half: 3 → 4Reversed: 4 → 3 → nullStep 3: Mergeorig=1, newhead=4Iteration 1:temp1=2, temp2=31.next=4, 4.next=2orig=2, newhead=3List: 1 → 4 → 2 → 3Iteration 2:temp1=null (2.next was originally 3 but we cut at slow=2, so 2.next = null... wait)Actually after cutting at slow=2, first half is 1 → 2 → null, so orig when it becomes 2, orig.next = null.temp1 = orig.next = nulltemp2 = newhead.next = null2.next = 3, 3.next = nullorig = null, newhead = nullnewhead is null → stopFinal result: 1 → 4 → 2 → 3 ✅Why slow.next = null Must Come After Saving newheadThis is a subtle but critical ordering detail in the code. Look at this sequence:ListNode newhead = reverse(slow.next); // save reversed second half FIRSTslow.next = null; // THEN cut the listIf you cut first (slow.next = null) and then try to reverse, you lose the reference to the second half entirely because slow.next is already null. Always save the second half reference before cutting.Time and Space ComplexityTime Complexity: O(n) — each of the three steps (find middle, reverse, merge) makes a single pass through the list. Total is 3 passes = O(3n) = O(n).Space Complexity: O(1) — everything is done by rearranging pointers in place. No extra arrays, no recursion stack, no additional data structures. Just a handful of pointer variables.This is the optimal solution — linear time and constant space.Alternative Approach — Using ArrayList (Simpler but O(n) Space)If you find the three-step approach hard to implement under interview pressure, here is a simpler approach using extra space:public void reorderList(ListNode head) { // store all nodes in ArrayList for random access List<ListNode> nodes = new ArrayList<>(); ListNode curr = head; while (curr != null) { nodes.add(curr); curr = curr.next; } int left = 0; int right = nodes.size() - 1; while (left < right) { nodes.get(left).next = nodes.get(right); left++; if (left == right) break; // odd number of nodes nodes.get(right).next = nodes.get(left); right--; } nodes.get(left).next = null; // terminate the list}This is much easier to understand and code. Store all nodes in an ArrayList, use two pointers from both ends, and wire up the next pointers.Time Complexity: O(n) Space Complexity: O(n) — ArrayList stores all nodesThis is acceptable in most interviews. Mention the O(1) space approach as the optimal solution if asked.Common Mistakes to AvoidNot cutting the list before merging If you do not set slow.next = null after finding the middle, the first half still points into the second half. During merging, this creates cycles and infinite loops. Always cut before merging.Wrong loop condition for finding the middle The condition fast.next != null && fast.next.next != null ensures fast does not go out of bounds when jumping two steps. Using just fast != null && fast.next != null moves slow one step too far for even-length lists.Looping on orig instead of newhead The merge loop should run while newhead != null, not while orig != null. The second half is always shorter or equal to the first half. Once the second half is done, the remaining first half is already correctly placed.Forgetting to save both temp pointers before rewiring In the merge step, you must save both orig.next and newhead.next before changing any pointers. Changing orig.next first and then trying to access orig.next to save it gives you the wrong node.How This Problem Combines Multiple PatternsThis problem is special because it does not rely on a single technique. It is a combination of three fundamental linked list operations:Fast & Slow Pointer — you saw this concept in problems like finding the middle of a list and detecting cycles (LeetCode 141, 142).Reverse a Linked List — the most fundamental linked list operation, appears in LeetCode 206 and as a subtask in dozens of problems.Merge Two Lists — similar to merging two sorted lists (LeetCode 21) but here order is not sorted, it is alternating.Solving this problem proves you are comfortable with all three patterns individually and can combine them when needed.FAQs — People Also AskQ1. What is the most efficient approach for LeetCode 143 Reorder List? The three-step approach — find middle with fast/slow pointer, reverse second half, merge alternately — runs in O(n) time and O(1) space. It is the optimal solution. The ArrayList approach is O(n) time and O(n) space but simpler to code.Q2. Why use fast and slow pointer to find the middle? Because a singly linked list has no way to access elements by index. You cannot just do list[length/2]. The fast and slow pointer technique finds the middle in a single pass without knowing the length beforehand.Q3. Why reverse the second half instead of the first half? The problem wants front-to-back alternation. If you reverse the second half, its first node is the original last node — exactly what you need to interleave with the front of the first half. Reversing the first half would give the wrong order.Q4. What is the time complexity of LeetCode 143? O(n) time for three linear passes (find middle, reverse, merge). O(1) space since all operations are in-place pointer manipulations with no extra data structures.Q5. Is LeetCode 143 asked in coding interviews? Yes, frequently at companies like Amazon, Google, Facebook, and Microsoft. It is considered a benchmark problem for linked list mastery because it requires combining three separate techniques cleanly under pressure.Similar LeetCode Problems to Practice Next206. Reverse Linked List — Easy — foundation for step 2 of this problem876. Middle of the Linked List — Easy — fast & slow pointer isolated21. Merge Two Sorted Lists — Easy — merging technique foundation234. Palindrome Linked List — Easy — also uses find middle + reverse second half148. Sort List — Medium — merge sort on linked list, uses same split techniqueConclusionLeetCode 143 Reorder List is one of the best Medium linked list problems because it forces you to think in multiple steps and combine techniques rather than apply a single pattern. The fast/slow pointer finds the middle efficiently without knowing the length. Reversing the second half turns the "cannot go backwards" limitation of singly linked lists into a non-issue. And the alternating merge weaves everything together cleanly.Work through the dry runs carefully — especially the pointer saving step in the merge. Once you see why each step is necessary and how they connect, this problem will always feel approachable no matter when it shows up in an interview.

LeetCodeJavaLinked ListTwo PointerFast Slow PointerMedium