DSA

Find the intersection point of Y LL

Covers: With count nodes, With two pointers. Optimal — Time O(m+n), Space O(1).

August 8, 2026

With count nodes#

Count the lengths of both lists. Advance the pointer on the longer list by |len1 - len2| steps so both pointers are equidistant from the end. Then move both pointers forward in sync — the first node where they meet is the intersection. The key insight is that the intersection node is at the same distance from the end in both lists, so equalizing the starting positions aligns them. The recursive CountNodes uses O(m+n) stack space; replacing it with an iterative count brings space down to O(1).

cpp

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:

    int CountNodes(ListNode* head)
    {
        if(!head)
            return 0;
        return 1 + CountNodes(head->next);
    }

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

        ListNode* p = headA;
        ListNode* q = headB;

        if(!p || !q)
            return NULL;

        int count1 = CountNodes(p);
        int count2 = CountNodes(q);

        int d= abs(count1-count2);

        if(count1>count2)
        {
            while(d--)
                p=p->next;
        }else{
            while(d--)
                q=q->next;
        }

        while(p && q && p!=q)
        {
            p=p->next;
            q=q->next;
        }
        if(p==q)
            return q;
        return NULL;
    }
};

Time Complexity:O(m + n), where m and n are the lengths of the two linked lists because the CountNodes function traverses each list once, and the final while loop can iterate at most min(m, n) times.

Space Complexity:O(m + n) due to the recursive calls of CountNodes function which can go upto the size of linked lists in worst case.

With two pointers#

Each pointer starts at a different list head. When it reaches the end of its list it is redirected to the head of the other list. After at most m + n steps both pointers will have traveled the same total distance and will be at the same node — the intersection (or both null if there is none). This works because redirecting effectively equalizes the path lengths without needing to compute them explicitly, achieving O(1) space.

cpp

/*
Definition of singly linked list:
struct ListNode
{
    int val;
    ListNode *next;
    ListNode()
    {
        val = 0;
        next = NULL;
    }
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
    }
    ListNode(int data1, ListNode *next1)
    {
        val = data1;
        next = next1;
    }
};
*/

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* pointerOne = headA;
        ListNode* pointerTwo = headB;

        while(pointerOne != pointerTwo){
            pointerOne = pointerOne ? pointerOne->next : headB;
            pointerTwo = pointerTwo ? pointerTwo->next : headA;
        }

        return pointerTwo;

    }
};

Time Complexity:O(m+n) where m and n are the lengths of the two linked lists.

Space Complexity:O(1) because it uses a constant amount of extra space.

DSAOdd Even Linked ListIn-place pointer weaving — odd indices first, then even. Optimal — Time O(n), Space O(1).DSARotate ListCovers: Naive, Optimal (circular link). Optimal — Time O(n), Space O(1).DSAReverse Linked ListCovers: Iterative, Recursive. Optimal — Time O(n), Space O(n).

With count nodes#

With two pointers#

Related articles