📅Day-16 Striver’s SDE Sheet | Linked List Part 2 | Find intersection point of Y LinkedList, Detect a cycle in Linked List.

Note : Started my 27-day DSA journey with Striver’s SDE Sheet!
I will be journaling every day — recording what I learn, reflecting on it, and sharing it with my network to help fellow learners and aspiring developers.. Learning through videos, resources, and the internet — simplifying logic in my own way with real-world connections. Sharing 2 questions daily: brute-force to optimal, clean Java code, time & space complexity, and key patterns.

This blog series is for anyone preparing for coding interviews — whether you’re a beginner or a revision warrior. Let’s grow together! 🚀

Namaste Developers! 🙏

Welcome to Day 16 of my 27-day DSA journey using Striver’s SDE Sheet!

1️⃣ Find intersection of Two Linked Lists

🔸 Problem Statement:

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.

For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

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

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

• intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.

• listA - The first linked list.

• listB - The second linked list.

• skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.

• skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

Example 2:

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Constraints:

• The number of nodes of listA is in the m.

• The number of nodes of listB is in the n.

• 1 <= m, n <= 3 * 10<sup>4</sup>

• 1 <= Node.val <= 10<sup>5</sup>

• 0 <= skipA <= m

• 0 <= skipB <= n

• intersectVal is 0 if listA and listB do not intersect.

• intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

Follow up: Could you write a solution that runs inO(m + n)time and use onlyO(1)memory?

💠Real-Life Example

Imagine two friends walking on different paths in a park .

• Friend A starts from Gate A.

• Friend B starts from Gate B.

• They meet at the fountain (intersection).

If one friend walks slower, they’ll take longer. But if both keep walking and switch gates after finishing, they’ll always meet at the fountain at the same time.

This is exactly what our two-pointer solution does.

💠Brute Force

📍 Idea: Compare each node of list A with every node of list B until we find a match.

Steps:

1. For each node in listA, loop through all nodes in listB.

2. If A == B (same memory reference, not just value), that’s the intersection.

3. If no match, return null.

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA;
        while (a != null) {
            ListNode b = headB;
            while (b != null) {
                if (a == b) return a;  // intersection found
                b = b.next;
            }
            a = a.next;
        }
        return null;
    }
}

📍Complexity:

• Time: O(m * n) (nested loops, bad for large inputs)

• Space: O(1) (no extra space)

This works but is super slow when m, n ≈ 30,000

💠Optimal Approach

📍 Instead of brute force, we can use two pointers.

💡 Trick: If one pointer reaches the end, move it to the start of the other list. This way, they will align and eventually meet at the intersection (or both end up null if no intersection).

Steps:

1. Take two pointers pA (on listA) and pB (on listB).

2. Move them one step at a time.

3. If a pointer reaches the end, redirect it to the other list’s head.

4. They will either meet at the intersection OR both become null.

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

        ListNode pA = headA, pB = headB;

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

        return pA; // intersection node OR null
    }
}

Complexity:

• Time: O(m + n) ✅ (each pointer traverses both lists at most once)

• Space: O(1) ✅ (no extra space)

Much faster and cleaner!

---

2️⃣Linked List Cycle

🔸 Problem Statement:

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

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Return true if there is a cycle in the linked list. Otherwise, return false.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints:

• The number of the nodes in the list is in the range [0, 10<sup>4</sup>].

• -10<sup>5</sup> <= Node.val <= 10<sup>5</sup>

• pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

💠Real-Life Example

Think of a circular race track.

• If two people (one fast and one slow ) are running, then:

  • If the track is circular (cycle hai), the fast one will eventually lap the slow one.

  • If the track is straight (no cycle), the fast one will reach the end and stop, while the slow one never gets caught.

This is exactly how we detect a cycle in a linked list!

💠Another Real-World Example

Imagine a WhatsApp group where:

• Every person has a "next person" to forward a message.

• If the chain of forwards eventually comes back to you (loop) → that’s a cycle.

• If messages keep rea

• ching new people until nobody is left → that’s a non-cyclic list.

In linked lists:

• HashSet approach is like keeping a record of who already got the message.

• Tortoise & Hare approach is like having 2 people forwarding at different speeds – if they meet again, then obviously a cycle exists!

💠Brute Force Approach (Using HashSet)

• Traverse the linked list and keep storing visited nodes in a HashSet.

• If we ever reach a node that is already in the set → cycle detected.

• If we reach null → no cycle.

class Solution {
    public boolean hasCycle(ListNode head) {
        // For every node, check ahead if cycle exists
        ListNode curr = head;

        while (curr != null) {
            ListNode checker = curr.next;

            // Look ahead from current node
            while (checker != null) {
                if (checker == curr) {
                    return true; // cycle detected
                }
                checker = checker.next;
            }

            curr = curr.next;
        }

        return false; // reached end, no cycle
    }
}

💠Complexity :

• Time Complexity → O(n²)

• Space Complexity → O(1)

⚠️ Because of O(n²) time, this brute force solution will almost always give TLE on large test cases.

💠Optimal Approach (Floyd’s Cycle Detection / Tortoise & Hare Algorithm)

• Use two pointers:

  • Slow → moves one step at a time

  • Fast → moves two steps at a time

• If there’s no cycle, fast will reach null.

• If there’s a cycle, fast and slow will eventually meet.

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

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;       // move 1 step
            fast = fast.next.next;  // move 2 steps

            if (slow == fast) {
                return true; // cycle detected
            }
        }
        return false; // no cycle
    }
}

💠 Complexity:

• Time Complexity: O(N)

Both pointers traverse nodes linearly.

• Space Complexity: O(1)

We use only two pointers, constant extra space.

👉 This is the optimal solution for cycle detection.

---

✍️ Final Notes:

If you're just starting your DSA journey like me, don't worry if you don’t get it perfect the first time.
Visualize → Dry Run → Optimize.
Stay consistent, and let’s crack every problem from brute to optimal! 💪

🙏 Special Thanks

A heartfelt thank you to Rajvikraaditya Sir for creating and sharing such an incredible DSA resource with the community (takeuforward). Your structured approach has made DSA more accessible and less intimidating for thousands of learners like me.

If this helped you, do share it with your fellow DSA learners.
Comment with your doubts — I’d love to answer and grow together 🌱

✍️ Payal Kumari 👩‍💻
My 27-Day DSA Journey with Striver’s Sheet! #dsawithpayal