Find the Duplicate Number: Binary Search and Fast/Slow Pointers (No Array Modification, O(1) Space)
Given n+1 integers in the range [1,n], find the unique duplicate without modifying the array and using only O(1) extra space. Solve it with value-range binary search and Floyd's cycle detection (fast/slow pointers), with implementations in C, C++, and JavaScript.
2145 words
|
11 minutes
Reversing a Singly Linked List: Iterative and Recursive Approaches Explained (Whole List / First N Nodes / Range / K-Group)
Master both iterative and recursive solutions for reversing a singly linked list, and apply these two approaches to four classic problems: reversing the entire list, reversing the first N nodes, reversing a range, and reversing in groups of K. Includes implementations in C, C++, and JavaScript.
2845 words
|
14 minutes
Detecting a Cycle in a Singly Linked List and Finding Its Start: Floyd's Cycle Detection Algorithm
First use fast and slow pointers to determine whether a linked list has a cycle; if it does, locate the entry node of the cycle by moving at equal speed. A combination of two classic problems: Floyd's cycle detection plus the mathematical proof for the cycle start. Includes implementations in C, C++, and JavaScript.
1200 words
|
6 minutes
Detecting Intersection of Two Singly Linked Lists and Finding the Intersection Node: Two-Pointer Alternating Traversal
Determine whether two singly linked lists intersect, and if so, find the intersection node. The two-pointer alternating traversal method works by having pA jump to the head of pB after reaching the end, and pB jump to the head of pA after reaching the end, so the two pointers eventually meet at the intersection node or both become null. Includes implementations in C, C++, and JavaScript.
1053 words
|
5 minutes
Finding the Kth Node from the End of a Singly Linked List: Two-Pointer Gap Method
Find the Kth node from the end of a singly linked list in just one pass. Use the two-pointer technique: fast moves K steps ahead, then slow and fast advance together, so when fast reaches the end, slow is exactly at the target position. Includes implementations in C, C++, and JavaScript.
862 words
|
4 minutes
Merge K Sorted Lists: Min-Heap vs. Divide and Conquer
Merge K ascending linked lists into a single ascending linked list. Covers two approaches: a min-heap (priority queue) and divide-and-conquer pairwise merging, with an analysis of their trade-offs. Includes implementations in C, C++, and JavaScript.
1412 words
|
7 minutes
Merge Two Sorted Linked Lists: Two Pointers and a Dummy Node
Merge two ascending linked lists into a single ascending linked list. Use two pointers to compare node values one by one, and a dummy head node to handle edge cases uniformly. Includes implementations in C, C++, and JavaScript.
859 words
|
4 minutes
Finding the Middle of a Singly Linked List: The Classic Fast and Slow Pointer Technique
Use the fast and slow pointer technique to find the middle node of a singly linked list in one pass. The slow pointer moves one step at a time while the fast pointer moves two; when fast reaches the end, slow is exactly at the midpoint. Includes implementations in C, C++, and JavaScript.
865 words
|
4 minutes