Leet Code : Intersection of Two Linked ListsLeet Code – Java | Python | C++ | Dart | Easy Solution

20 / 100

Find the location where two linked lists intersect.


Find the node where the two linked lists cross when there are two of them and the tail of the second list points to a node in the first list.

Take into account the linked lists below, where the fourth node of the first list is connected to the tail of the second list. The intersection point, node 4, should be the solution’s return value.

Leet Code : Intersection of Two Linked ListsLeet Code - Java | Python | C++ | Dart | Easy Solution
Leet Code : Intersection of Two Linked ListsLeet Code - Java | Python | C++ | Dart | Easy Solution 2

1) Consider each node in the first list and determine whether it can be accessed from the second list as a straightforward solution. The intersection point is the first node in the first list that can be reached from the second list. The total number of nodes in the first and second lists, m and n, respectively, determine the solution’s time complexity, which is O(m.n).

1.Utilizing Hashing


The plan is to go through the first list and put the addresses of each node in a hash table. the address of the first node that is present in the hash table by traversing the second list. The intersection would happen at this node. The idea’s implementation in C++, Java, and Python is as follows:

The solution is not ideal, though. This article offers a summary of a number of runtime improvement options.

C++ :

#include <iostream>
#include <unordered_set>
using namespace std;
 
// A Linked List Node
struct Node
{
    int data;
    Node* next;
};
 
// Utility function to create a new node with the given data and
// pushes it onto the list's front
void push(Node*& headRef, int data)
{
    // create a new linked list node from the heap
    Node* newNode = new Node;
 
    newNode->data = data;
    newNode->next = headRef;
    headRef = newNode;
}
 
// Function to find the intersection point of two linked lists using hashing
Node* findIntersection(Node* first, Node* second)
{
    // maintain a set to store list nodes
    unordered_set<Node*> nodes;
 
    // traverse the first list and insert the address of each node into the set
    while (first)
    {
        nodes.insert(first);
        first = first->next;
    }
 
    // now traverse the second list and find the first node that is
    // already present in the set
    while (second)
    {
        // return the current node if it is found in the set
        if (nodes.find(second) != nodes.end()) {
            return second;
        }
        second = second->next;
    }
 
    // we reach here if lists do not intersect
    return nullptr;
}
 
int main()
{
    // construct the first linked list (1 —> 2 —> 3 —> 4 —> 5 —> null)
    Node* first = nullptr;
    for (int i = 5; i > 0; i--) {
        push(first, i);
    }
 
    // construct the second linked list (1 —> 2 —> 3 —> null)
    Node* second = nullptr;
    for (int i = 3; i > 0; i--) {
        push(second, i);
    }
 
    // link tail of the second list to the fourth node of the first list
    second->next->next->next = first->next->next->next;
 
    Node* addr = findIntersection(first, second);
    if (addr) {
        cout << "The intersection point is " << addr->data << endl;
    }
    else {
        cout << "The lists do not intersect." << endl;
    }
 
    return 0;
}
import java.util.HashSet;
import java.util.Set;
 
// A Linked List Node
class Node
{
    int data;
    Node next;
}
 
class Main
{
    // Utility function to create a new node with the given data and
    // pushes it onto the list's front
    public static Node push(Node head, int data)
    {
        Node node = new Node();
        node.data = data;
        node.next = head;
        return node;
    }
 
    // Function to find the intersection point of two linked lists using hashing
    public static Node findIntersection(Node first, Node second)
    {
        // maintain a set to store list nodes
        Set<Node> nodes = new HashSet<>();
 
        // traverse the first list and insert the address of each node into the set
        while (first != null)
        {
            nodes.add(first);
            first = first.next;
        }
 
        // now traverse the second list and find the first node that is
        // already present in the set
        while (second != null)
        {
            // return the current node if it is found in the set
            if (nodes.contains(second)) {
                return second;
            }
            second = second.next;
        }
 
        // we reach here if lists do not intersect
        return null;
    }
 
    public static void main(String[] args)
    {
        // construct the first linked list (1 —> 2 —> 3 —> 4 —> 5 —> null)
        Node first = null;
        for (int i = 5; i > 0; i--) {
            first = push(first, i);
        }
 
        // construct the second linked list (1 —> 2 —> 3 —> null)
        Node second = null;
        for (int i = 3; i > 0; i--) {
            second = push(second, i);
        }
 
        // link tail of the second list to the fourth node of the first list
        second.next.next.next = first.next.next.next;
 
        Node addr = findIntersection(first, second);
        if (addr != null) {
            System.out.println("The intersection point is " + addr.data);
        }
        else {
            System.out.println("The lists do not intersect.");
        }
    }
}
# A Linked List Node
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
 
 
# Function to find the intersection point of two linked lists using hashing
def findIntersection(first, second):
 
    # maintain a set to store list nodes
    nodes = set()
 
    # traverse the first list and insert the address of each node into the set
    while first:
        nodes.add(first)
        first = first.next
 
    # now traverse the second list and find the first node that is
    # already present in the set
    while second:
        # return the current node if it is found in the set
        if second in nodes:
            return second
        second = second.next
 
    # we reach here if lists do not intersect
    return None
 
 
if __name__ == '__main__':
 
    # construct the first linked list (1 —> 2 —> 3 —> 4 —> 5 —> None)
    first = None
    for i in reversed(range(1, 6)):
        first = Node(i, first)
 
    # construct the second linked list (1 —> 2 —> 3 —> None)
    second = None
    for i in reversed(range(1, 4)):
        second = Node(i, second)
 
    # link tail of the second list to the fourth node of the first list
    second.next.next.next = first.next.next.next
 
    addr = findIntersection(first, second)
    if addr:
        print('The intersection point is', addr.data)
    else:
        print('The lists do not intersect.')

Time and Space Complextity analysis

The total number of nodes in the first and second lists, m and n, respectively, determine the time complexity of the aforementioned solution, which is O(m + n). To store the first list’s nodes in a hash table, the programme needs O(m) additional space.

2.Making use of the Floyd’s Cycle Detection Algorithm


Making the first linked list circular by connecting its tail to its head is another strategy. Finding a loop in the second linked list is therefore the only issue left.

The aim is to use Floyd’s cycle detection approach to obtain a pointer to the loop node, and then use that loop node, let’s say k, to calculate the total number of nodes in the loop. After that, pick two pointers, one pointing to the head node and the other to the k’th node from the head. These pointers will eventually collide at the initial node of the loop if we concurrently move them at the same pace.

In C++, Java, and Python, the algorithm can be implemented as follows:

#include <iostream>
#include <unordered_set>
using namespace std;
 
// A Linked List Node
struct Node
{
    int data;
    Node* next;
};
 
// Utility function to create a new node with the given data and
// pushes it onto the list's front
void push(Node*& headRef, int data)
{
    // create a new linked list node from the heap
    Node* newNode = new Node;
 
    newNode->data = data;
    newNode->next = headRef;
    headRef = newNode;
}
 
// Find the starting node of the loop in a linked list pointed by `head`.
// The `loopNode` points to one of the nodes involved in the cycle
Node* removeCycle(Node* loopNode, Node* head)
{
    // find the count of nodes involved in the loop and store the count in `k`
    int k = 1;
    for (Node* ptr = loopNode; ptr->next != loopNode; ptr = ptr->next) {
        k++;
    }
 
    // get pointer to k'th node from the head
    Node* curr = head;
    for (int i = 0; i < k; i++) {
        curr = curr->next;
    }
 
    // simultaneously move the `head` and `curr` pointers
    // at the same speed until they meet
    while (curr != head)
    {
        curr = curr->next;
        head = head->next;
    }
 
    // `curr` now points to the starting node of the loop
    return curr;
}
 
// Function to identify a cycle in a linked list using
// Floyd’s cycle detection algorithm
Node* identifyCycle(Node* head)
{
    // take two pointers – `slow` and `fast`
    Node *slow = head, *fast = head;
 
    while (fast && fast->next)
    {
        // move slow by one pointer
        slow = slow->next;
 
        // move fast by two pointers
        fast = fast->next->next;
 
        // if they meet any node, the linked list contains a cycle
        if (slow == fast) {
            return slow;
        }
    }
 
    // return null if the linked list does not contain a cycle
    return nullptr;
}
 
// Function to find the intersection point of two linked lists
Node* findIntersection(Node* first, Node* second)
{
    Node* prev = nullptr;       // previous pointer
    Node* curr = first;         // main pointer
 
    // traverse the first list
    while (curr)
    {
        // update the previous pointer to the current node and
        // move the main pointer to the next node
        prev = curr;
        curr = curr->next;
    }
 
    // create a cycle in the first list
    if (prev) {
        prev->next = first;
    }
 
    // now get a pointer to the loop node using the second list
    Node* slow = identifyCycle(second);
 
    // find the intersection node
    Node* addr = nullptr;
    if (slow) {
        addr = removeCycle(slow, second);
    }
 
    // remove cycle in the first list before exiting
    if (prev) {
        prev->next = nullptr;
    }
 
    // return the intersection node
    return addr;
}
 
int main()
{
    // construct the first linked list (1 —> 2 —> 3 —> 4 —> 5 —> null)
    Node* first = nullptr;
    for (int i = 7; i > 0; i--) {
        push(first, i);
    }
 
    // construct the second linked list (1 —> 2 —> 3 —> null)
    Node* second = nullptr;
    for (int i = 3; i > 0; i--) {
        push(second, i);
    }
 
    // link tail of the second list to the fourth node of the first list
    second->next->next->next = first->next->next->next;
 
    Node* addr = findIntersection(first, second);
    if (addr) {
        cout << "The intersection point is " << addr->data << endl;
    }
    else {
        cout << "The lists do not intersect." << endl;
    }
 
    return 0;
}
// A Linked List Node
class Node
{
    int data;
    Node next;
}
 
class Main
{
    // Utility function to create a new node with the given data and
    // pushes it onto the list's front
    public static Node push(Node head, int data)
    {
        Node node = new Node();
        node.data = data;
        node.next = head;
        return node;
    }
 
    // Find the starting node of the loop in a linked list pointed by `head`.
    // The `loopNode` points to one of the nodes involved in the cycle
    public static Node removeCycle(Node loopNode, Node head)
    {
        // find the count of nodes involved in the loop and store the count in `k`
        int k = 1;
        for (Node ptr = loopNode; ptr.next != loopNode; ptr = ptr.next) {
            k++;
        }
 
        // get pointer to k'th node from the head
        Node curr = head;
        for (int i = 0; i < k; i++) {
            curr = curr.next;
        }
 
        // simultaneously move the `head` and `curr` pointers
        // at the same speed until they meet
        while (curr != head)
        {
            curr = curr.next;
            head = head.next;
        }
 
        // `curr` now points to the starting node of the loop
        return curr;
    }
 
    // Function to identify a cycle in a linked list using
    // Floyd’s cycle detection algorithm
    public static Node identifyCycle(Node head)
    {
        // take two pointers – `slow` and `fast`
        Node slow = head, fast = head;
        while (fast != null && fast.next != null)
        {
            // move slow by one pointer
            slow = slow.next;
 
            // move fast by two pointers
            fast = fast.next.next;
 
            // if they meet any node, the linked list contains a cycle
            if (slow == fast) {
                return slow;
            }
        }
 
        // return null if the linked list does not contain a cycle
        return null;
    }
 
    // Function to find the intersection point of two linked lists
    public static Node findIntersection(Node first, Node second)
    {
        Node prev = null;       // previous pointer
        Node curr = first;      // main pointer
 
        // traverse the first list
        while (curr != null)
        {
            // update the previous pointer to the current node and
            // move the main pointer to the next node
            prev = curr;
            curr = curr.next;
        }
 
        // create a cycle in the first list
        if (prev != null) {
            prev.next = first;
        }
 
        // now get a pointer to the loop node using the second list
        Node slow = identifyCycle(second);
 
        // find the intersection node
        Node addr = null;
        if (slow != null) {
            addr = removeCycle(slow, second);
        }
 
        // remove cycle in the first list before exiting
        if (prev != null) {
            prev.next = null;
        }
 
        // return the intersection node
        return addr;
    }
 
    public static void main(String[] args)
    {
        // construct the first linked list (1 —> 2 —> 3 —> 4 —> 5 —> null)
        Node first = null;
        for (int i = 7; i > 0; i--) {
            first = push(first, i);
        }
 
        // construct the second linked list (1 —> 2 —> 3 —> null)
        Node second = null;
        for (int i = 3; i > 0; i--) {
            second = push(second, i);
        }
 
        // link tail of the second list to the fourth node of the first list
        second.next.next.next = first.next.next.next;
 
        Node addr = findIntersection(first, second);
        if (addr != null) {
            System.out.println("The intersection point is " + addr.data);
        }
        else {
            System.out.println("The lists do not intersect");
        }
    }
}
# A Linked List Node
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
 
 
# Find the starting node of the loop in a linked list pointed by `head`.
# The `loop_node` points to one of the nodes involved in the cycle
def removeCycle(loop_node, head):
 
    # find the count of nodes involved in the loop and store the count in `k`
    k = 1
    ptr = loop_node
    while ptr.next is not loop_node:
        k += 1
        ptr = ptr.next
 
    # get pointer to k'th node from the head
    curr = head
    for _ in range(k):
        curr = curr.next
 
    # simultaneously move the `head` and `curr` pointers
    # at the same speed until they meet
    while curr is not head:
        curr = curr.next
        head = head.next
 
    # `curr` now points to the starting node of the loop
    return curr
 
 
# Function to identify a cycle in a linked list using
# Floyd’s cycle detection algorithm
def identifyCycle(head):
 
    # take two pointers – `slow` and `fast`
    slow = fast = head
 
    while fast and fast.next:
        # move slow by one pointer
        slow = slow.next
 
        # move fast by two pointers
        fast = fast.next.next
 
        # if they meet any node, the linked list contains a cycle
        if slow == fast:
            return slow
 
    # return None if the linked list does not contain a cycle
    return None
 
 
# Function to find the intersection point of two linked lists
def findIntersection(first, second):
    prev = None         # previous pointer
    curr = first        # main pointer
 
    # traverse the first list
    while curr:
        # update the previous pointer to the current node and
        # move the main pointer to the next node
        prev = curr
        curr = curr.next
 
    # create a cycle in the first list
    if prev:
        prev.next = first
 
    # now get a pointer to the loop node using the second list
    slow = identifyCycle(second)
 
    # find the intersection node
    addr = None
    if slow:
        addr = removeCycle(slow, second)
 
    # remove cycle in the first list before exiting
    if prev:
        prev.next = None
 
    # return the intersection node
    return addr
 
 
if __name__ == '__main__':
 
    # construct the first linked list (1 —> 2 —> 3 —> 4 —> 5 —> None)
    first = None
    for i in reversed(range(1, 6)):
        first = Node(i, first)
 
    # construct the second linked list (1 —> 2 —> 3 —> None)
    second = None
    for i in reversed(range(1, 4)):
        second = Node(i, second)
 
    # link tail of the second list to the fourth node of the first list
    second.next.next.next = first.next.next.next
 
    addr = findIntersection(first, second)
    if addr:
        print('The intersection point is', addr.data)
    else:
        print('The lists do not intersect.')

Time and Space Complextity analysis

The time complexity of the above solution is O(m + n), where m and n are the total number of nodes in the first and second list, respectively.

3.Making use of various node counts


Finding the intersection point may also be done by comparing the number of nodes in the two lists. The goal is to move the larger list forward by k nodes, where k is the number of nodes that differ between the two lists. Once they cross, both lists should be moved at the same speed. The intersection point is the node at which both lists come together.

Python, C++, and Java all support the following implementation of this logic:

#include <iostream>
using namespace std;
 
// A Linked List Node
struct Node
{
    int data;
    Node* next;
};
 
// Utility function to create a new node with the given data and
// pushes it onto the list's front
void push(Node*& headRef, int data)
{
    // create a new linked list node from the heap
    Node* newNode = new Node;
 
    newNode->data = data;
    newNode->next = headRef;
    headRef = newNode;
}
 
// Utility function to find the total number of nodes in a linked list
int size(Node* head)
{
    int nodes = 0;
    for (Node* curr = head; curr != nullptr; curr = curr->next) {
        nodes++;
    }
    return nodes;
}
 
// Function to find the intersection point of two linked lists.
// Assume that the first list contains `k` nodes more than the second list
Node* findIntersection(Node* first, Node* second, int k)
{
    // advance the bigger list by `k` nodes
    for (int i = 0; i < k && first; i++) {
        first = first->next;
    }
 
    // simultaneously move both lists at the same speed until they meet
    while (first && second)
    {
        // if both lists meet any node, then that node is the intersection point
        if (first == second) {
            return first;
        }
 
        // advance both lists by one node
        first = first->next;
        second = second->next;
    }
 
    // return null if both lists don't meet
    return nullptr;
}
 
// Function to find the intersection point of two linked lists
Node* findIntersection(Node* first, Node* second)
{
    // get the difference in the number of nodes in both lists
    int diff = size(first) - size(second);
 
    // if the first list has a smaller number of nodes, exchange both lists
    if (diff < 0) {
        swap(first, second);
    }
 
    // find and return the intersection node
    return findIntersection(first, second, abs(diff));
}
 
int main()
{
    // construct the first linked list (1 —> 2 —> 3 —> 4 —> 5 —> null)
    Node* first = nullptr;
    for (int i = 7; i > 0; i--) {
        push(first, i);
    }
 
    // construct the second linked list (1 —> 2 —> 3 —> null)
    Node* second = nullptr;
    for (int i = 3; i > 0; i--) {
        push(second, i);
    }
 
    // link tail of the second list to the fourth node of the first list
    second->next->next->next = first->next->next->next;
 
    Node* addr = findIntersection(first, second);
    if (addr) {
        cout << "The intersection point is " << addr->data << endl;
    }
    else {
        cout << "The lists do not intersect." << endl;
    }
 
    return 0;
}
// A Linked List Node
class Node
{
    int data;
    Node next;
}
 
class Main
{
    // Utility function to create a new node with the given data and
    // pushes it onto the list's front
    public static Node push(Node head, int data)
    {
        Node node = new Node();
        node.data = data;
        node.next = head;
        return node;
    }
 
    // Utility function to find the total number of nodes in a linked list
    public static int size(Node head)
    {
        int nodes = 0;
        for (Node curr = head; curr != null; curr = curr.next) {
            nodes++;
        }
        return nodes;
    }
 
    // Function to find the intersection point of two linked lists.
    // Assume that the first list contains `k` nodes more than the second list
    public static Node findIntersection(Node first, Node second, int k)
    {
        // advance the bigger list by `k` nodes
        for (int i = 0; i < k && first!= null; i++) {
            first = first.next;
        }
 
        // simultaneously move both lists at the same speed until they meet
        while (first != null && second != null)
        {
            // if both lists meet any node, then that node is the intersection point
            if (first == second) {
                return first;
            }
 
            // advance both lists by one node
            first = first.next;
            second = second.next;
        }
 
        // return null if both lists don't meet
        return null;
    }
 
    // Function to find the intersection point of two linked lists
    public static Node findIntersection(Node first, Node second)
    {
        // get the difference in the number of nodes in both lists
        int diff = size(first) - size(second);
 
        // if the first list has a smaller number of nodes, exchange both lists
        if (diff < 0)
        {
            Node node = first;
            first = second;
            second = node;
        }
 
        // find and return the intersection node
        return findIntersection(first, second, Math.abs(diff));
    }
 
 
    public static void main(String[] args)
    {
        // construct the first linked list (1 —> 2 —> 3 —> 4 —> 5 —> null)
        Node first = null;
        for (int i = 7; i > 0; i--) {
            first = push(first, i);
        }
 
        // construct the second linked list (1 —> 2 —> 3 —> null)
        Node second = null;
        for (int i = 3; i > 0; i--) {
            second = push(second, i);
        }
 
        // link tail of the second list to the fourth node of the first list
        second.next.next.next = first.next.next.next;
 
        Node addr = findIntersection(first, second);
        if (addr != null) {
            System.out.println("The intersection point is " + addr.data);
        }
        else {
            System.out.println("The lists do not intersect.");
        }
    }
}
# A Linked List Node
class Node:
    def __init__(self, data, next = None):
        self.data = data
        self.next = next
 
 
# Utility function to find the total number of nodes in a linked list
def size(head):
    nodes = 0
    while head:
        nodes += 1
        head = head.next
    return nodes
 
 
# Function to find the intersection point of two linked lists.
# Assume that the first list contains `k` nodes more than the second list
def findIntersection(first, second, k):
 
    # advance the bigger list by `k` nodes
    i = 0
    while i < k and first:
        first = first.next
        i += 1
 
    # simultaneously move both lists at the same speed until they meet
    while first and second:
        # if both lists meet any node, then that node is the intersection point
        if first == second:
            return first
        # advance both lists by one node
        first = first.next
        second = second.next
 
    # return None if both lists don't meet
    return None
 
 
# Function to find the intersection point of two linked lists
def findIntersectionPt(first, second):
 
    # get the difference in the number of nodes in both lists
    diff = size(first) - size(second)
 
    # if the first list has a smaller number of nodes, exchange both lists
    if diff < 0:
        node = first
        first = second
        second = node
 
    # find and return the intersection node
    return findIntersection(first, second, abs(diff))
 
 
if __name__ == '__main__':
 
    # construct the first linked list (1 —> 2 —> 3 —> 4 —> 5 —> None)
    first = None
    for i in reversed(range(1, 6)):
        first = Node(i, first)
 
    # construct the second linked list (1 —> 2 —> 3 —> None)
    second = None
    for i in reversed(range(1, 4)):
        second = Node(i, second)
 
    # link tail of the second list to the fourth node of the first list
    second.next.next.next = first.next.next.next
 
    addr = findIntersectionPt(first, second)
    if addr:
        print('The intersection point is', addr.data)
    else:
        print('The lists do not intersect.')

4.Using distance from intersection point

The total nodes in the first list plus the separation between the head of the second list and the intersection point equals the total nodes in the second list plus the separation between the head of the first list and the intersection point.

The plan is to use two pointers, x and y, which will initially refer to the first and second lists’ heads, respectively. Once they arrive at a common node, both points should go forward at the same rate. Send x to the top of the second list when it reaches its conclusion. Turn y to the top of the first list when it reaches its conclusion. The intersection node is the location where x and y converge.

The following is how the method may be used in

#include <iostream>
using namespace std;
 
// A Linked List Node
struct Node
{
    int data;
    Node* next;
};
 
// Utility function to create a new node with the given data and
// pushes it onto the list's front
void push(Node*& headRef, int data)
{
    // create a new linked list node from the heap
    Node* newNode = new Node;
 
    newNode->data = data;
    newNode->next = headRef;
    headRef = newNode;
}
 
// Function to find the intersection point of two linked lists
Node* findIntersection(Node* first, Node* second)
{
    // Take two pointers pointing to the heads of respective lists
    Node *x = first, *y = second;
 
    // advance both pointers until they meet at a common node
    while (x != y)
    {
        // When the first list reaches its end, redirect it to the
        // head of the second list
        if (x == nullptr) {
            x = second;
        }
        else {
            x = x->next;
        }
 
        // When the second list reaches its end, redirect it to the
        // head of the first list
        if (y == nullptr) {
            y = first;
        }
        else {
            y = y->next;
        }
    }
 
    // return the common node
    return x;
}
 
int main()
{
    // construct the first linked list (1 —> 2 —> 3 —> 4 —> 5 —> null)
    Node* first = nullptr;
    for (int i = 7; i > 0; i--) {
        push(first, i);
    }
 
    // construct the second linked list (1 —> 2 —> 3 —> null)
    Node* second = nullptr;
    for (int i = 3; i > 0; i--) {
        push(second, i);
    }
 
    // link tail of the second list to the fourth node of the first list
    second->next->next->next = first->next->next->next;
 
    Node* addr = findIntersection(first, second);
    if (addr) {
        cout << "The intersection point is " << addr->data << endl;
    }
    else {
        cout << "The lists do not intersect." << endl;
    }
 
    return 0;
}
// A Linked List Node
class Node
{
    int data;
    Node next;
}
 
class Main
{
    // Utility function to create a new node with the given data and
    // pushes it onto the list's front
    public static Node push(Node head, int data)
    {
        // create a new linked list node from the heap
        Node node = new Node();
        node.data = data;
        node.next = head;
 
        return node;
    }
 
    // Function to find the intersection point of two linked lists
    public static Node findIntersection(Node first, Node second)
    {
        // Take two pointers pointing to the heads of respective lists
        Node x = first, y = second;
 
        // advance both pointers until they meet at a common node
        while (x != y)
        {
            // When the first list reaches its end, redirect it to the
            // head of the second list
            if (x == null) {
                x = second;
            }
            else {
                x = x.next;
            }
 
            // When the second list reaches its end, redirect it to the
            // head of the first list
            if (y == null) {
                y = first;
            }
            else {
                y = y.next;
            }
        }
 
        // return the common node
        return x;
    }
 
    public static void main(String[] args)
    {
        // construct the first linked list (1 —> 2 —> 3 —> 4 —> 5 —> null)
        Node first = null;
        for (int i = 7; i > 0; i--) {
            first = push(first, i);
        }
 
        // construct the second linked list (1 —> 2 —> 3 —> null)
        Node second = null;
        for (int i = 3; i > 0; i--) {
            second = push(second, i);
        }
 
        // link tail of the second list to the fourth node of the first list
        second.next.next.next = first.next.next.next;
 
        Node addr = findIntersection(first, second);
        if (addr != null) {
            System.out.println("The intersection point is " + addr.data);
        }
        else {
            System.out.println("The lists do not intersect.");
        }
    }
}
# A Linked List Node
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next
 
 
# Function to find the intersection point of two linked lists
def findIntersection(first, second):
 
    # Take two pointers pointing to the heads of respective lists
    x = first
    y = second
 
    # advance both pointers until they meet at a common node
    while x != y:
 
        # When the first list reaches its end, redirect it to the
        # head of the second list
        if x is None:
            x = second
        else:
            x = x.next
 
        # When the second list reaches its end, redirect it to the
        # head of the first list
        if y is None:
            y = first
        else:
            y = y.next
 
    # return the common node
    return x
 
 
if __name__ == '__main__':
 
    # construct the first linked list (1 —> 2 —> 3 —> 4 —> 5 —> None)
    first = None
    for i in reversed(range(1, 6)):
        first = Node(i, first)
 
    # construct the second linked list (1 —> 2 —> 3 —> None)
    second = None
    for i in reversed(range(1, 4)):
        second = Node(i, second)
 
    # link tail of the second list to the fourth node of the first list
    second.next.next.next = first.next.next.next
 
    addr = findIntersection(first, second)
    if addr:
        print('The intersection point is', addr.data)
    else:
        print('The lists do not intersect.')

Time and Space Complextity analysis

The above solution has a time complexity of O(m + n), where m and n are the total number of nodes in the first and second lists, respectively.

Leave a Comment