Finding the Intersection Node of Two Linked Lists

In this problem, we will be given two linked lists. The linked lists will be merged at a node of both the linked lists, forming a Y-shaped list. We have to find the node at which the linked lists merge.

Let us see some examples to understand the question

Input:

List1 = 1 -> 2 -> 3 -> 4 -> 5

List2 = 9 -> 8 -> 4 -> 5

Output: 4

The two lists merge after node 4 of both linked lists

Method - 1

The most basic approach to solving this problem is to use a nested loop. The outer loop will traverse through every node of the first list, and the inner while loop will traverse through the second loop. The inner while loop will check if the current node of list 2 is the same as the current node of list 1. If the condition is satisfied, then we have found the intersection node. If the loop ends without finding the intersection node, then we will return None.

Below is the Python program for the implementation of the above approach.

Code

# Python program to find the intersection node of the two linked lists

# Creating a constructor class to create a node object
class Node:
  def __init__(self, val):
    self.val = val
    self.next = None

# Defining a function that will take the two linked lists and return the intersection of the two linked lists
def getMergingNode(list1, list2):

  # Starting the outer while loop, which will traverse through the nodes of list1
  while list1:
    t = list2

    # Starting the inner while loop, which will traverse through the nodes of list2
    while t:
      # Checking if the nodes of both lists are the same
      if t == list1:
        return list1
      t = t.next
    list1 = list1.next

  # If the intersection is not present, then we will return None
  return None

# Creating two linked lists
list1 = Node(1)
list1.next = Node(2)
list1.next.next = Node(3)
common1 = Node(4)
common2 = Node(5)
list1.next.next.next = common1
list1.next.next.next.next = common2
list2 = Node(9)
list2.next = Node(8)
list2.next.next = common1
list2.next.next.next = common2

intersectionNode = getMergingNode(list1, list2)

if not intersectionNode:
  print("There is no intersection point in the two linked lists")
else:
  print("The intersection node is:", intersectionNode.val)

Output:

The intersection node is: 4

Time Complexity: Due to the nested loop, the time complexity of this program will be O(m * n). Here, m and n are the number of nodes in the two linked lists.

Space Complexity: We are not using any extra space; hence, the space complexity is constant.

Method - 2

In this approach, we will use a different structure of the linked list. We will make some modifications to the basic structure, which will help us to solve this problem. We will add a new variable to the linked list, which will store the Boolean value True or False. This variable will keep track of whether a node is already visited or not.

We will start by traversing the first linked list and mark all the nodes of the first linked list as visited. Then, we will traverse the second linked list. For each node, we will check if the node is already visited or not. If the node is already visited, that means we have visited that node in the first linked list, which implies that the linked lists intersect at this particular node. If we have completed the traversal of the second node without reaching a node that is already visited, that means the two linked lists do not intersect at any point. This approach is better than the previous approach as we are not using nested loops to traverse the linked lists. We will use linear traversal to find the intersection of the nodes.

Code

# Python program to find the intersection node of the linked lists using a new variable

# Creating a constructor class for the node
class Node:

  # Initializing the variables of the nodes of the linked list
  def __init__(self, data):
    self.data = data
    self.next = None

    # This variable will keep track of whether a node is already visited or not during the first linked list traversal
    self.visited = False
   
# Defining a function that will take the heads of the two linked lists and return if the two linked lists have a node of intersection or not
def getIntersectNode(list1, list2):
  t1 = list1

  # Traversing the first linked list and marking the visited variable of the nodes as True
  while(t1 is not None):
    t1.visited = True
    t1 = t1.next
   
  t2 = list2

  # Traversing the second linked list and checking if the current node of the list is already visited or not
  while(t2 is not None):

    # If the node is already visited, we will return the node as it will be the intersection node
    if(t2.visited):
      return t2.data
    else:
      t2.visited = True
    t2 = t2.next

  # If the function reaches this point, that means there is no point of intersection, and hence, we will return a False
  return False   
       
# Creating two linked lists
list1 = Node(1)
list1.next = Node(2)
list1.next.next = Node(3)
common1 = Node(4)
common2 = Node(5)
list1.next.next.next = common1
list1.next.next.next.next = common2
list2 = Node(9)
list2.next = Node(8)
list2.next.next = common1
list2.next.next.next = common2

intersectionNode = getIntersectNode(list1, list2)

if not intersectionNode:
  print("There is no intersection point in the two linked lists")
else:
  print("The intersection node is:", intersectionNode)

Output:

The intersection node is: 4

We do not need to create a new variable. We can use hash table too.

Code

# Python program to find the intersection node of the linked lists using a hash table

# Creating a constructor class for the node
class Node:

  # Initializing the variables of the nodes of the linked list
  def __init__(self, data):
    self.data = data
    self.next = None
   
# Defining a function that will take the heads of the two linked lists and return if the two linked lists have a node of intersection or not
def getIntersectNode(list1, list2):

  # Creating a list that will store the node
  # If a node is present in this list, that means that node is already visited; hence, it is the node of intersection
  vis = []
  t1 = list1

  # Traversing the first linked list and adding the nodes to the list of visited nodes
  while(t1 is not None):
    vis.append(t1)
    t1 = t1.next
   
  t2 = list2

  # Traversing the second linked list and checking if the current node of the list is already present in the visited node list or not
  while(t2 is not None):

    # If the node is already present in the list, we will return the node as it will be the intersection node
    if t2 in vis:
      return t2.data
    else:
      vis.append(t2)
    t2 = t2.next

  # If the function reaches this point, that means there is no point of intersection, and hence, we will return a False
  return False   
       
# Creating two linked lists
list1 = Node(1)
list1.next = Node(2)
list1.next.next = Node(3)
common1 = Node(4)
common2 = Node(5)
list1.next.next.next = common1
list1.next.next.next.next = common2
list2 = Node(9)
list2.next = Node(8)
list2.next.next = common1
list2.next.next.next = common2

intersectionNode = getIntersectNode(list1, list2)

if not intersectionNode:
  print("There is no intersection point in the two linked lists")
else:
  print("The intersection node is:", intersectionNode)

Output:

The intersection node is: 4

Time Complexity: We are traversing both lists once. To traverse the lists, we have used a linear loop. Therefore, the time complexity of traversing will be the sum of the lengths of both the linked lists. Hence, the time complexity will be O(m + n). m and n are the lengths of the two linked lists. We are taking total lengths because, in the worst-case scenario, the linked lists will not have any intersection, and in that case, complete linked lists will be traversed.

Auxiliary space: We have created a list to store the nodes that are already visited. The nodes will be stored only once. Therefore, the space complexity will be the length of this list. In the worst-case scenario, the length of this list will be O( max(m, n) ), where max(m, n) is the length of the longer linked lists out of the two.

Method - 3

In this approach, we will make use of the difference in the count of the two linked lists to find the intersection node of the two linked lists.

We will follow these steps to solve this problem.

Firstly, we will count the number of nodes present in the first linked list.
Then, we will find the count of the number of nodes present in the second linked list.
We will then find the difference between the number of nodes of the two linked lists. Let this difference be stored as diff.
Now, we have to traverse the linked lists with the greater number of nodes. We will traverse this list starting from the first node to the dth node of the list. From the dth node forward, both the linked lists have the same number of nodes.
Now, we will run another loop for traversing both of the linked lists together. We will traverse the lists parallel and check if there is any common node. The first common node of the two lists will be the node of intersection.
If we do not find any intersection node, we will return False.

Below is the Python code for this approach.

Code

# Python program to find the intersection node of the linked lists using a hash table

# Creating a constructor class for the node
class Node:

  # Initializing the variables of the nodes of the linked list
  def __init__(self, val):
    self.val = val
    self.next = None

# Defining the function to count the number of nodes present in the linked list
def Count(node):
    cur = node
    count = 0
    while cur is not None:
        count += 1
        cur = cur.next
    return count

# Defining a function that will take the heads of the two linked lists and return if the two linked lists have a node of intersection or not 
def getMergingNode(list1, list2):
   
    # Getting the total number of elements in the first linked list
    c1 = Count(list1)
   
    # Geting the total number of elements in the second linked list
    c2 = Count(list2)

    #Traverse the bigger node by 'd' so that from that node onwards, both LinkedList would have to have the same number of nodes, and we can traverse them together.
    if c1 > c2:
        d = c1 - c2
    else:
        d = c2 - c1
        list1, list2 = list2, list1
    
    curr1 = list1
    curr2 = list2

    # Traversing the longer list using a for loop
    for i in range(d):
        if curr1 is None:
            return -1
        curr1 = curr1.next
    
    while curr1 is not None and curr2 is not None:
        # For the intersection the nodes addresss must be same and not just the value. Therefore, we will check if the two nodes are same and not check if the values are same.
        if curr1 is curr2:
            return curr1
     
        curr1 = curr1.next
        curr2 = curr2.next
   
    # If we are not able to find the intersection node then return -1
    return -1
     

# Creating two linked lists
list1 = Node(1)
list1.next = Node(2)
list1.next.next = Node(3)
common1 = Node(4)
common2 = Node(5)
list1.next.next.next = common1
list1.next.next.next.next = common2
list2 = Node(9)
list2.next = Node(8)
list2.next.next = common1
list2.next.next.next = common2

intersectionNode = getMergingNode(list1, list2)

if not intersectionNode:
  print("There is no intersection point in the two linked lists")
else:
  print("The intersection node is:", intersectionNode.val)

Output:

The intersection node is: 4

Time Complexity: O(m + n)

Auxiliary Space: O(1)

Method - 4

In this method, we will use hashing to find the intersection node. This method is similar to the method when we used a list to store the nodes that we have visited, except that this time, we will use a HashSet to store the nodes. The algorithm is simple. First, we will initialize an empty hash set. After initializing, we will traverse the first linked list and store all the nodes of this linked list in the hash set. In the next step, we will traverse the second linked list, and for each node, we will check if that node is in the hash set or not. If the node is in the hash set, that means it is the node of the intersection, and hence, we will return that node. If there is no node of intersection, the function will return False.

Code

# Python program to find the node of intersection for the given two linked lists

# Creating a constructor class to create a node object
class Node:
  def __init__(self, val):
    self.val = val
    self.next = None

# Defining a function to print the linked list
def Print(head):
  cur = head
  # Iterating over the linked list to print the node values
  while (cur != None):
    print(cur.val, end = " ")
    cur = cur.next
  print("")

# Defining a function that will take the two linked lists and return the intersection of the two linked lists
def getMergingNode(list1, list2):
   
  # Creating a HashSet to store the visited nodes of the linked list
  sett = set();

  # Iterating over the first linked list and adding the nodes to the HashSet
  while (list1 != None):
    sett.add(list1)
    list1 = list1.next

  # Iterating over the second linked list and checking if the nodes are in the HashSet
  while (list2 != None):

    # If the nodes are in the HashSet then return the node as that will be the intersection node
    if (list2 in sett):
      return list2;
    list2 = list2.next;
   
  # If the function has reached this step, then there is no intersection node in the two linked list
  return False;


# Creating two linked lists
list1 = Node(1)
list1.next = Node(2)
list1.next.next = Node(3)
common1 = Node(4)
common2 = Node(5)
list1.next.next.next = common1
list1.next.next.next.next = common2
list2 = Node(9)
list2.next = Node(8)
list2.next.next = common1
list2.next.next.next = common2

intersectionNode = getMergingNode(list1, list2)

if not intersectionNode:
  print("There is no intersection point in the two linked lists")
else:
  print("The intersection node is:", intersectionNode.val)

Output:

The intersection node is: 4

Time complexity: We are using two linear loops which will iterate till both of the linked lists are traversed; therefore the time complexity of the program is O( m + n )

Auxiliary Space: We have used extra space to store the nodes; therefore, the space complexity is linear, i.e., O(n).

Method - 5

In this method, we will use the famous two-pointer approach to find the intersection node. Here is the algorithm of this approach:

Firstly, we will initialize two pointers, which will point towards the head of the two linked lists. Let these pointers be p1 and p2, pointing towards list1 and list2.
Now, we will initialize a while loop. This while loop will continue until the point when the two pointers point towards the same node.
- In the while loop, we will move both of the pointers towards the next node of their respective linked lists.
- In the next step, we will check if both of the pointers point towards None. If this is the case, then the linked lists have no intersection node. Hence, we will return None.
- If any one of the pointer points towards None, then we will redirect it towards the head node of its linked list. That is, if p1 == None then p1 = list1 and if p2 == None then p2 = list2.
After some iterations, either both of the pointers will be pointing towards None or the intersection node. Hence, the while loop will be terminated.

Code

# Python program to find the node of intersection for the given two linked lists

# Creating a constructor class to create a node object
class Node:
  def __init__(self, val):
    self.val = val
    self.next = None

# Defining a function to print the linked list
def Print(head):
  cur = head
  # Iterating over the linked list to print the node values
  while (cur != None):
    print(cur.val, end = " ")
    cur = cur.next
  print("")

# Defining a function that will take the two linked lists and return the intersection of the two linked lists
def getMergingNode(list1, list2):

  # Initializing two pointers to traverse the two linked lists together
  p1 = list1
  p2 = list2

  # Checking if any of the pointer points to None.
  # If the pointer points to None, then there is no intersection node, so we will return None
  if (p1 == None or p2 == None):
    return None

  # Creating a while loop to traverse the two linked lists.
  # The loop will continue until we reach the intersection node
  while (p1 != p2):

    # Moving both of the pointers to the next node
    p1 = p1.next
    p2 = p2.next

    # Checking if the two pointers point towards the same node.
    # If the pointers point to the same node, that means it is the intersection node, and we will return the node
    if (p1 == p2):
      return p1

    # If the pointer of the first linked list points towards None, then we will point it towards the head of the second linked list
    if (p1 == None):
      p1 = list2

    # If the pointer of the second linked list points towards None, then we will point it towards the head of the first linked list
    if (p2 == None):
      p2 = list1

  return p1

# Creating two linked lists
list1 = Node(1)
list1.next = Node(2)
list1.next.next = Node(3)
common1 = Node(4)
common2 = Node(5)
list1.next.next.next = common1
list1.next.next.next.next = common2
list2 = Node(9)
list2.next = Node(8)
list2.next.next = common1
list2.next.next.next = common2

intersectionNode = getMergingNode(list1, list2)

if not intersectionNode:
  print("There is no intersection point in the two linked lists")
else:
  print("The intersection node is:", intersectionNode.val)

Output:

The intersection node is: 4

Time complexity: We are using a linear loop which will iterate till both of the linked lists are traversed; therefore the time complexity of the program is O( m + n )

Auxiliary Space: We have not created any extra space to store something; therefore, the space complexity is constant, i.e., O(1).

Method - 6

In this approach, we will use two stacks to find the intersection node. Firstly, we will initialize two stacks. In the next step, we will traverse both the linked lists and add all of the nodes of both of the linked lists to each of the stacks. Then, we will initialize a variable which will store the intersection node. Let this variable be merge_point = None. We will start a while loop, which will continue until the top elements of the stack are not equal. Inside the while loop, we will pop the top elements of the stack and store that node in the variable merge_point. When the while loop ends, we will return nerge_point, which will have the intersection node of the two linked lists. If there is no intersection point of the linked lists, then the while loop will not be executed, and merge_point = None will be returned.

Code

# Python program to find the node of intersection for the given two linked lists

# Creating a constructor class to create a node object
class Node:
  def __init__(self, val):
    self.val = val
    self.next = None

# Defining a function to print the linked list
def Print(head):
  cur = head
  # Iterating over the linked list to print the node values
  while (cur != None):
    print(cur.val, end = " ")
    cur = cur.next
  print("")

# Defining the function that will return the intersection node of the two linked lists
def getMergingNode(list1, list2):
    A = []
    B = []
    node = None
 
    while list2 != None:
        B.append(list2)
        list2 = list2.next
 
    while list1 != None:
        A.append(list1)
        list1 = list1.next
 
    if not A[-1].val == B[-1].val:
        return None
 
    while A and B and A[-1].val == B[-1].val:
        node = A[-1]
        A.pop()
        B.pop()
 
    return node
 
 
# Creating two linked lists
list1 = Node(1)
list1.next = Node(2)
list1.next.next = Node(3)
common1 = Node(4)
common2 = Node(5)
list1.next.next.next = common1
list1.next.next.next.next = common2
list2 = Node(9)
list2.next = Node(8)
list2.next.next = common1
list2.next.next.next = common2

intersectionNode = getMergingNode(list1, list2)

if not intersectionNode:
  print("There is no intersection point in the two linked lists")
else:
  print("The intersection node is:", intersectionNode.val)

Output:

The intersection node is: 4

Time Complexity: We are traversing both lists once. To traverse the lists, we have used a linear loop. Therefore, the time complexity of traversing will be the sum of the lengths of both the linked lists. Hence, the time complexity will be O(m + n). m and n are the lengths of the two linked lists. The while loop will take O(min(m, n)) in the worst-case scenario. Therefore, the average time complexity is O(m, n).

Auxiliary Space: We have created two stacks to store the nodes of both of the linked lists. The nodes will be stored only once. Therefore, the space complexity will be the total length of two stacks. Hence, the space complexity will be O(m + n).

Next TopicPython Solution of Median of Two Sorted Arrays

← prev next →