SvenStack

🧩 Problem Description

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list and return the new head.

Example:

1
2

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

💡 Intuition

This is similar to the merge step in merge sort.

At each step, compare the two current nodes:

• Choose the smaller one
• Move its pointer forward

🔢 Java Code (Iterative)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                curr.next = list1;
                list1 = list1.next;
            } else {
                curr.next = list2;
                list2 = list2.next;
            }
            curr = curr.next;
        }

        // Append remaining nodes
        curr.next = (list1 != null) ? list1 : list2;

        return dummy.next;
    }
}

🔁 Java Code (Recursive)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;

        if (list1.val <= list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n + m)
• Space Complexity:
  • Iterative: O(1)
  • Recursive: O(n + m) due to call stack

✍️ Summary

• A classic linked list problem — appears in merge sort, linked list manipulation, and more.
• Be comfortable with both iterative and recursive approaches.
• Dummy node makes code simpler and cleaner.

One of the most fundamental problems to master for linked list and recursion.

🧩 Problem Description

Given the head of a linked list, return the node where the cycle begins.
If there is no cycle, return null.

You must not modify the list.

Example:

1
2

Input: head = [3,2,0,-4], pos = 1 (tail connects to node at index 1)
Output: Node with value 2

💡 Step 1: Detect Cycle Using Two Pointers

Use Floyd’s Cycle Detection (Tortoise and Hare):

• slow moves one step, fast moves two steps.
• If they ever meet, there’s a cycle.
• ✅ Already used in lc-141

💡 Step 2: Find Entry Point of the Cycle

✨ Key Insight

Once slow and fast meet:

• Start a new pointer ptr1 from head.
• Start a second pointer ptr2 from where slow and fast met.
• Move both one step at a time.
• They will meet at the cycle entry.

📌 Why it works:
Let:

• L1 = distance from head to cycle start
• L2 = distance from cycle start to meeting point
• C = length of the cycle

Then:
2(L1 + L2) = L1 + L2 + kC ⟹ L1 = kC - L2
So moving L1 from head and L2 from meeting point leads to cycle start.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;

        ListNode slow = head;
        ListNode fast = head;

        // Step 1: Detect cycle
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                // Step 2: Find entry
                ListNode entry = head;
                while (entry != slow) {
                    entry = entry.next;
                    slow = slow.next;
                }
                return entry;
            }
        }

        return null;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)

✍️ Summary

• First detect cycle with two pointers.
• Then find the node where cycle begins by moving a new pointer from head.
• No extra memory needed — all in-place.

This is one of the most elegant applications of two-pointer technique in linked lists. Master it!

🧩 Problem Description

Given the head of a linked list, determine if the linked list has a cycle in it.

A cycle occurs when a node’s next pointer points to a previous node in the list.

Example:

1
2

Input: head = [3,2,0,-4], pos = 1 (tail connects to node index 1)
Output: true

💡 Brute Force (Not Recommended)

• Store visited nodes in a HashSet.
• If a node is already visited → cycle detected.

1
2
3
4
5
6
7
8
9

public boolean hasCycle(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    while (head != null) {
        if (visited.contains(head)) return true;
        visited.add(head);
        head = head.next;
    }
    return false;
}

• Time: O(n)
• Space: O(n)

💡 Optimal Approach: Floyd’s Tortoise and Hare

✨ Key Idea

• Use two pointers:
  • slow moves 1 step
  • fast moves 2 steps
• If there’s a cycle, fast will eventually “lap” slow.
• If fast reaches null, the list has no cycle.

🔢 Java Code (Two-Pointer Approach)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;

        ListNode slow = head;
        ListNode fast = head.next;

        while (slow != fast) {
            if (fast == null || fast.next == null) return false;
            slow = slow.next;
            fast = fast.next.next;
        }

        return true;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)

✍️ Summary

• This problem is a classic use case for Floyd’s Cycle Detection Algorithm.
• Know the difference:
  • lc-141: Detect existence of a cycle
  • lc-142: Find the starting node of the cycle

Learn the two-pointer cycle detection — it’s elegant and appears in many linked list problems.

🧩 Problem Description

Given the head of a singly linked list, return true if it is a palindrome, or false otherwise.

Example:

1
2
3
4
5

Input: 1 → 2 → 2 → 1
Output: true

Input: 1 → 2
Output: false

💡 Brute Force Idea

• Store values in a list or array.
• Check if the list is a palindrome.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

public boolean isPalindrome(ListNode head) {
    List<Integer> vals = new ArrayList<>();
    while (head != null) {
        vals.add(head.val);
        head = head.next;
    }
    int i = 0, j = vals.size() - 1;
    while (i < j) {
        if (!vals.get(i).equals(vals.get(j))) return false;
        i++;
        j--;
    }
    return true;
}

• Time: O(n)
• Space: O(n)
• ✅ Easy to implement, but not in-place.

💡 Optimal Approach (In-Place, O(1) Space)

✨ Strategy

1. Find the middle of the list (fast and slow pointers).
2. Reverse the second half.
3. Compare the two halves.
4. (Optional) Restore the list.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null) return true;

        // Step 1: Find middle
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Step 2: Reverse second half
        ListNode secondHalf = reverse(slow);

        // Step 3: Compare
        ListNode p1 = head, p2 = secondHalf;
        while (p2 != null) {
            if (p1.val != p2.val) return false;
            p1 = p1.next;
            p2 = p2.next;
        }

        return true;
    }

    private ListNode reverse(ListNode head) {
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)

✍️ Summary

• Key techniques used:
  • Fast/slow pointer
  • In-place list reversal
  • Two-pointer comparison
• This approach keeps space minimal while maintaining correctness.

This is a great example of combining several core linked list techniques in a single elegant solution.

🧩 Problem Description

Given the head of a singly linked list, reverse the list and return the new head.

Example:

1
2

Input: 1 → 2 → 3 → 4 → 5
Output: 5 → 4 → 3 → 2 → 1

💡 Brute Force (Not In-Place)

• Store values in an array or stack, then rebuild the list.
• ❌ Not optimal — uses extra space.

💡 Optimal Approach: Iterative In-Place Reversal

✨ Key Idea

• Use 3 pointers:
  • prev to track the previous node.
  • curr as the current node.
  • next to temporarily hold curr.next.

At each step:

• Reverse the link: curr.next = prev
• Move forward

🔢 Java Code (Iterative)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }

        return prev;
    }
}

🔁 Java Code (Recursive)

1
2
3
4
5
6
7
8
9
10
11

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode reversed = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return reversed;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity:
  • Iterative: O(1)
  • Recursive: O(n) (due to recursion stack)

✍️ Summary

• This is a fundamental linked list pattern — useful in many real problems (e.g., palindrome check, list reordering).
• Understand both iterative and recursive versions.

Learn it well — this reversal logic appears often in interviews and linked list puzzles.

🧩 Problem Description

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.

The linked lists must retain their original structure after the function returns.

Example:

1
2
3
4

Input:
A: 4 → 1 → 8 → 4 → 5
B: 5 → 6 → 1 → 8 → 4 → 5
Output: Reference to node with value 8

💡 Brute Force (Not Ideal)

• Compare every node from headA with every node from headB.
• Time: O(m × n)
• ❌ Inefficient

💡 Optimal Approach: Two Pointers

✨ Key Idea

• Use two pointers pA and pB.
• Traverse both lists:
  • If pA reaches end, redirect it to headB.
  • If pB reaches end, redirect it to headA.
• They will either meet at the intersection node or both become null (no intersection).

Why it works:

• Both pointers traverse exactly m + n steps.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;

        ListNode pA = headA;
        ListNode pB = headB;

        while (pA != pB) {
            pA = (pA == null) ? headB : pA.next;
            pB = (pB == null) ? headA : pB.next;
        }

        return pA;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(m + n)
• Space Complexity: O(1)

✍️ Summary

• This is a textbook two-pointer technique for linked lists.
• Avoids using extra space like hash sets.
• Useful for related problems such as:
  • lc-142: Linked List Cycle II
  • lc-21: Merge Two Sorted Lists

Pointer redirection is a simple yet powerful technique when dealing with linked lists of unequal lengths.

🧩 Problem Description

Write an efficient algorithm that searches for a value in an m x n matrix.

This matrix has the following properties:

• Integers in each row are sorted in ascending order.
• Integers in each column are sorted in ascending order.

Example:

1
2
3
4
5
6
7
8
9

Input: matrix = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
], target = 5

Output: true

💡 Naive Approach (Not Ideal)

• Scan the whole matrix: O(m × n) time.
• ❌ Not efficient considering the sorted properties.

💡 Optimal Approach: Search from Top-Right Corner

✨ Key Idea

• Start from the top-right cell.
• At each step:
  • If the value is equal to target, return true.
  • If the value is greater than target, move left.
  • If the value is less than target, move down.
• Why it works:
  • Rows increase left → right.
  • Columns increase top → bottom.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int m = matrix.length;
        int n = matrix[0].length;

        int row = 0;
        int col = n - 1;

        while (row < m && col >= 0) {
            int val = matrix[row][col];
            if (val == target) {
                return true;
            } else if (val > target) {
                col--;
            } else {
                row++;
            }
        }

        return false;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(m + n)
  Worst case: we move from top-right to bottom-left.
• Space Complexity: O(1)
  No extra space used.

✍️ Summary

• The staircase search pattern is a must-know technique for sorted 2D matrices.
• It’s more efficient than binary search on each row or column separately.
• Similar sorted matrix problems:
  • lc-74 (Search a 2D Matrix)
  • lc-378 (Kth Smallest Element in a Sorted Matrix)

When rows and columns are sorted, think about combining row and column movement strategies instead of brute force search.

🧩 Problem Description

You are given an n x n 2D matrix representing an image. Rotate the image 90 degrees clockwise.

You must rotate the image in place.

Example:

1
2

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [[7,4,1],[8,5,2],[9,6,3]]

💡 Brute Force Approach (Not Allowed)

• Create a new matrix and write rotated values into it.
• ❌ Uses O(n²) extra space, violates “in-place” requirement.

💡 Optimal Approach: Transpose + Reverse

✨ Key Idea

1. Transpose the matrix:
   • Swap matrix[i][j] with matrix[j][i] for all i < j.
2. Reverse each row.

This combination achieves a 90-degree clockwise rotation in place.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;

        // Step 1: Transpose
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }

        // Step 2: Reverse each row
        for (int i = 0; i < n; i++) {
            reverseRow(matrix[i]);
        }
    }

    private void reverseRow(int[] row) {
        int left = 0, right = row.length - 1;
        while (left < right) {
            int temp = row[left];
            row[left] = row[right];
            row[right] = temp;
            left++;
            right--;
        }
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n²)
  Each element is processed twice (transpose + reverse).
• Space Complexity: O(1)
  Fully in-place.

✍️ Summary

• The transpose + reverse method is an elegant solution for in-place rotation problems.
• Remember:
  • Clockwise → transpose + reverse rows
  • Counterclockwise → transpose + reverse columns
• This is a core pattern in matrix transformation problems.

Mastering in-place matrix tricks helps with both interviews and real-world image manipulation tasks.

🧩 Problem Description

Given an m x n matrix, return all elements of the matrix in spiral order.

Example:

1
2

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,6,9,8,7,4,5]

💡 Approach: Layer-by-Layer Traversal

✨ Key Idea

We maintain four boundaries:

• top, bottom, left, right

At each step:

1. Traverse from left to right along top.
2. Traverse from top + 1 to bottom along right.
3. Traverse from right - 1 to left along bottom (only if top < bottom).
4. Traverse from bottom - 1 to top + 1 along left (only if left < right).

After each step, we shrink the boundaries inward.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

import java.util.*;

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();

        if (matrix == null || matrix.length == 0) return result;

        int top = 0, bottom = matrix.length - 1;
        int left = 0, right = matrix[0].length - 1;

        while (top <= bottom && left <= right) {
            // Traverse from left to right
            for (int j = left; j <= right; j++) {
                result.add(matrix[top][j]);
            }
            top++;

            // Traverse from top to bottom
            for (int i = top; i <= bottom; i++) {
                result.add(matrix[i][right]);
            }
            right--;

            if (top <= bottom) {
                // Traverse from right to left
                for (int j = right; j >= left; j--) {
                    result.add(matrix[bottom][j]);
                }
                bottom--;
            }

            if (left <= right) {
                // Traverse from bottom to top
                for (int i = bottom; i >= top; i--) {
                    result.add(matrix[i][left]);
                }
                left++;
            }
        }

        return result;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(m × n)
  Each cell is visited exactly once.
• Space Complexity: O(1) extra space
  (excluding output list)

✍️ Summary

• Boundary shrinking is a classic matrix traversal technique.
• Spiral order appears in related problems like Spiral Matrix II (filling numbers), lc-59.
• Make sure to check conditions carefully when shrinking boundaries to avoid duplicates.

Matrix traversal patterns (row-wise, column-wise, spiral, zigzag) are common interview topics — good to master!

🧩 Problem Description

Given an m x n integer matrix, if an element is 0, set its entire row and column to 0.
You must do it in place.

Example:

1
2

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

💡 Brute Force (Not Ideal)

• Mark all rows and columns with zeros using extra sets.
• Time: O(m × n)
• Space: O(m + n) → uses extra memory, not fully in-place.

💡 Optimal Approach: Constant Space Using First Row and Column

✨ Key Idea

• Use the first row and first column as markers for rows and columns that need to be zeroed.
• Two passes:
  1. Mark rows/columns.
  2. Set cells to zero based on markers.
• Special care is needed for handling the first row and column separately.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

class Solution {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean firstRowZero = false;
        boolean firstColZero = false;

        // Check if first row needs to be zeroed
        for (int j = 0; j < n; j++) {
            if (matrix[0][j] == 0) {
                firstRowZero = true;
                break;
            }
        }

        // Check if first column needs to be zeroed
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0) {
                firstColZero = true;
                break;
            }
        }

        // Use first row and column as markers
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }

        // Zero cells based on markers
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }

        // Zero first row if needed
        if (firstRowZero) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }

        // Zero first column if needed
        if (firstColZero) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(m × n)
  Two passes over the matrix.
• Space Complexity: O(1)
  No extra space beyond the matrix itself.

✍️ Summary

• Smart use of the matrix itself as storage avoids extra space usage.
• Watch out for the first row and first column edge cases.
• Similar in-place patterns appear in other matrix transformation problems.

Learning how to reuse input space for flags is a useful technique in constrained-space algorithm design.