SvenStack

🧩 Problem Description

A linked list is given where each node has two pointers:

• next: points to the next node
• random: can point to any node in the list or be null

Return a deep copy of the list.

Each node in the new list must have the same value and the same random structure — but must be a new node, not shared.

💬 Example

1
2
3
4
5
6
7

Input:
Node1: val = 7, next = Node2, random = null
Node2: val = 13, next = Node3, random = Node1
...

Output:
Deep copy of the above structure

💡 Approach 1: HashMap Mapping (Straightforward)

✨ Idea

• Traverse original list, and use a HashMap<OldNode, NewNode> to:
  • Store the mapping between original nodes and copied ones
  • After building the copy, set the next and random pointers

🔢 Java Code (Using HashMap)

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

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        Map<Node, Node> map = new HashMap<>();

        // Step 1: Create all nodes and store mapping
        Node curr = head;
        while (curr != null) {
            map.put(curr, new Node(curr.val));
            curr = curr.next;
        }

        // Step 2: Assign next and random pointers
        curr = head;
        while (curr != null) {
            Node copy = map.get(curr);
            copy.next = map.get(curr.next);
            copy.random = map.get(curr.random);
            curr = curr.next;
        }

        return map.get(head);
    }
}

• Time Complexity: O(n)
• Space Complexity: O(n) — due to the map

💡 Approach 2: Interleaving Nodes (O(1) Extra Space)

✨ Key Idea

1. Clone each node and insert it right after the original:
   • A → A' → B → B' → ...
2. Assign random pointers:
   A'.random = A.random.next
3. Detach the new list from the original

🔢 Java Code (No Extra Space)

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

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return null;

        // Step 1: Clone and insert nodes
        Node curr = head;
        while (curr != null) {
            Node clone = new Node(curr.val);
            clone.next = curr.next;
            curr.next = clone;
            curr = clone.next;
        }

        // Step 2: Assign random pointers
        curr = head;
        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }

        // Step 3: Detach the clone list
        Node dummy = new Node(0);
        Node copyCurr = dummy;
        curr = head;

        while (curr != null) {
            Node clone = curr.next;
            copyCurr.next = clone;
            copyCurr = clone;

            curr.next = clone.next;  // Restore original list
            curr = curr.next;
        }

        return dummy.next;
    }
}

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

✍️ Summary

• Understand how to maintain relationships with .random using either:
  • Hash map mapping (O(n) space)
  • Interleaved list strategy (O(1) space)
• This is a deep copy problem with pointer manipulation — commonly tested in interviews

Practice building clones of linked structures while preserving complex references. This is a great test of both logic and implementation skill.

🧩 Problem Description

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

• Nodes that remain fewer than k at the end should remain in order.
• You may not alter the values in the list’s nodes — only node pointers may be changed.

💬 Example

1
2

Input: head = [1,2,3,4,5], k = 3
Output: [3,2,1,4,5]

💡 Intuition

This is an extension of basic linked list reversal.

• Reversing k nodes at a time → similar to lc-206, but in segments.
• Key steps:
  1. Check if at least k nodes remain.
  2. Reverse k nodes.
  3. Recurse or loop to the next k-group.

✅ Use a helper function to reverse a portion of the list.

🔢 Java Code (Recursive)

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

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode curr = head;
        int count = 0;

        // Step 1: Check if we have at least k nodes
        while (curr != null && count < k) {
            curr = curr.next;
            count++;
        }

        if (count < k) return head;

        // Step 2: Reverse k nodes
        ListNode prev = null;
        curr = head;
        for (int i = 0; i < k; i++) {
            ListNode nextTemp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextTemp;
        }

        // Step 3: Recursively reverse next k group
        head.next = reverseKGroup(curr, k);

        return prev;
    }
}

🔁 Java Code (Iterative with Dummy Node)

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

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode dummy = new ListNode(0, head);
        ListNode prevGroupEnd = dummy;

        while (true) {
            ListNode kth = getKthNode(prevGroupEnd, k);
            if (kth == null) break;

            ListNode groupStart = prevGroupEnd.next;
            ListNode nextGroupStart = kth.next;

            // Reverse current k-group
            ListNode prev = kth.next, curr = groupStart;
            while (curr != nextGroupStart) {
                ListNode tmp = curr.next;
                curr.next = prev;
                prev = curr;
                curr = tmp;
            }

            // Connect with previous part
            prevGroupEnd.next = kth;
            prevGroupEnd = groupStart;
        }

        return dummy.next;
    }

    private ListNode getKthNode(ListNode curr, int k) {
        while (curr != null && k > 0) {
            curr = curr.next;
            k--;
        }
        return curr;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n), each node is visited once
• Space Complexity:
  • Recursive: O(n/k) recursion stack
  • Iterative: O(1)

✍️ Summary

• Advanced linked list problem — combines segment reversal, pointer manipulation, and recursion/looping.
• You must understand lc-206 (reverse linked list) first.
• Mastering this problem improves your skill with pointer operations.

Start from simpler problems like lc-24, then build up to this level. Great interview question!

🧩 Problem Description

Given the head of a linked list, swap every two adjacent nodes and return its head.

You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

💬 Example

1
2

Input: head = [1,2,3,4]
Output: [2,1,4,3]

💡 Intuition

This is a classic linked list node manipulation problem.

• Use a dummy node to simplify edge cases.
• Iterate through the list in pairs.
• For each pair:
  • Update pointers to swap the two nodes.
  • Move to the next pair.

🔢 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 swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode curr = dummy;

        while (curr.next != null && curr.next.next != null) {
            ListNode first = curr.next;
            ListNode second = curr.next.next;

            // Swapping nodes
            first.next = second.next;
            second.next = first;
            curr.next = second;

            // Move to next pair
            curr = first;
        }

        return dummy.next;
    }
}

🔁 Java Code (Recursive)

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

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

        ListNode first = head;
        ListNode second = head.next;

        first.next = swapPairs(second.next);
        second.next = first;

        return second;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(n), where n is the number of nodes
• Space Complexity:
  • Iterative: O(1)
  • Recursive: O(n) due to recursion stack

✍️ Summary

• Good test of pointer manipulation in linked lists.
• Practice both iterative and recursive approaches.
• Understanding node-level swaps is essential for problems like:
  • lc-25: Reverse Nodes in k-Group
  • lc-92: Reverse Linked List II

Dummy nodes make linked list problems so much easier — use them!

🧩 Problem Description

Given the head of a linked list, remove the n-th node from the end of the list and return its head.

💬 Example

1
2

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

💡 Intuition

Use the two-pointer technique:

1. Move first pointer n steps ahead.
2. Then move both first and second together until first reaches the end.
3. Now second is just before the node to delete.

✅ Trick: use a dummy node before head to simplify edge cases like deleting the head.

🔢 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

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode first = dummy;
        ListNode second = dummy;

        // Move first n+1 steps to maintain gap
        for (int i = 0; i <= n; i++) {
            first = first.next;
        }

        // Move both pointers
        while (first != null) {
            first = first.next;
            second = second.next;
        }

        // Skip the target node
        second.next = second.next.next;

        return dummy.next;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(L), where L is the length of the list
• Space Complexity: O(1)

✍️ Summary

• Two-pointer pattern is super useful for problems involving relative positions.
• Using a dummy node helps avoid corner-case bugs when deleting the head.
• This technique appears frequently — make sure you’re confident with it.

Similar problems include:

• lc-876: Middle of the Linked List
• lc-160: Intersection of Two Linked Lists
• lc-234: Palindrome Linked List

🧩 Problem Description

Given two integers dividend and divisor, divide them without using multiplication, division, or mod operator.

Return the quotient after dividing dividend by divisor.

The result should be truncated toward zero (i.e., 8.9 → 8, -8.9 → -8).

💬 Example

1
2
3
4
5

Input: dividend = 10, divisor = 3
Output: 3

Input: dividend = 7, divisor = -3
Output: -2

⚠️ Constraints

• You must not use *, /, or %.
• Range of inputs: -2³¹ ≤ dividend, divisor ≤ 2³¹ - 1
• If result overflows (> 2³¹ - 1), return 2³¹ - 1

💡 Intuition

To simulate division:

• Keep subtracting the divisor from dividend until the dividend is smaller than divisor.
• To speed up, use bit shifting (double the divisor each time).

This is like long division: find the largest multiple of divisor that fits in dividend.

🔢 Java Code (Bit Manipulation)

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

class Solution {
    public int divide(int dividend, int divisor) {
        // Edge case: overflow
        if (dividend == Integer.MIN_VALUE && divisor == -1) return Integer.MAX_VALUE;

        // Use long to prevent overflow during shifting
        long a = Math.abs((long) dividend);
        long b = Math.abs((long) divisor);
        int result = 0;

        while (a >= b) {
            long temp = b;
            int multiple = 1;
            while (a >= (temp << 1)) {
                temp <<= 1;
                multiple <<= 1;
            }
            a -= temp;
            result += multiple;
        }

        // Determine sign
        return (dividend > 0) == (divisor > 0) ? result : -result;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(log N) — where N is |dividend|
• Space Complexity: O(1)

✍️ Summary

• No multiplication, division, or modulus — use bit shifts and subtraction.
• Carefully handle:
  • Negative numbers
  • Edge cases like Integer.MIN_VALUE / -1
• This is a good exercise in low-level arithmetic logic.

Learn this if you want to understand how division could be implemented in systems without direct hardware division support.

🧩 Problem Description

You are given two non-empty linked lists representing two non-negative integers.
The digits are stored in reverse order, and each node contains a single digit.

Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

💬 Example

1
2
3
4
5

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]

Explanation:
342 + 465 = 807

💡 Intuition

• Since the numbers are stored in reverse, we can simulate digit-by-digit addition like grade school.
• Maintain a carry variable for overflow.
• Traverse both lists and construct the result 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

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);  // Dummy head
        ListNode curr = dummy;
        int carry = 0;

        while (l1 != null || l2 != null || carry > 0) {
            int sum = carry;

            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }

            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }

            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
        }

        return dummy.next;
    }
}

⏱ Time and Space Complexity

• Time Complexity: O(max(n, m)) — traverses both lists once
• Space Complexity: O(max(n, m)) — result list size

✍️ Summary

• This is a classic linked list and math simulation problem.
• Be comfortable managing carry and dummy nodes.
• Appears frequently in interviews and serves as a great test of logic + list handling.

For follow-ups, consider:

• BigInteger usage (if languages allow)
• Lists in forward order (lc-445)

🧩 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.