Find the intersection point of two linked lists
Given two linked lists, where the tail of the second list points to a node in the first list, find the node where both lists intersect.
Consider the following linked lists where the tail of the second list is connected to the fourth node of the first list. The solution should return a pointer to node 4 as the intersection point.
A simple solution is to consider each node of the first list and check if it can be reached from the second list. The first node in the first list that is reachable from the second list is the intersection point. The time complexity of this solution is O(m.n), where m and n are the total number of nodes in the first and second list, respectively.
However, the solution is far from optimal. This post provides an overview of several alternatives to improve the runtime.
1. Using Hashing
The idea is to traverse the first list and store each node’s address in a hash table. Then traverse the second list and get the address of the first node present in the hash table. This node would be the intersection point. Following is the C++, Java, and Python implementation based on the idea:
C++
|
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 |
#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; } |
Output:
The intersection point is 4
Java
|
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
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."); } } } |
Output:
The intersection point is 4
Python
|
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 41 42 43 44 45 46 47 48 49 50 51 |
# 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.') |
Output:
The intersection point is 4
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. However, the program uses O(m) additional space for storing nodes of the first list in a hash table.
2. Using Floyd’s Cycle Detection Algorithm
Another approach is to make the first linked list circular by linking its tail to the head. Then the problem reduces to finding a loop in the second linked list.
The idea is to get a pointer to the loop node using Floyd’s cycle detection algorithm and count the total number of nodes in the loop using that loop node, say k. Then take two pointers – one pointing to the head node and another pointing to the k'th node from the head. If we simultaneously move these pointers at the same speed, they will eventually meet at the loop’s starting node.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 |
#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; } |
Output:
The intersection point is 4
Java
|
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 |
// 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"); } } } |
Output:
The intersection point is 4
Python
|
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
# 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.') |
Output:
The intersection point is 4
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. Using difference in node counts
We can also use the difference in node counts of both lists to find the intersection point. The idea is to advance the bigger list by k nodes, where k is the difference in the number of nodes in both lists. Then move both lists at the same speed until they intersect with each other. The node at which both lists intersect is the intersection point.
This logic can be implemented as follows in C++, Java, and Python:
C++
|
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
#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; } |
Output:
The intersection point is 4
Java
|
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
// 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."); } } } |
Output:
The intersection point is 4
Python
|
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 |
# 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.') |
Output:
The intersection point is 4
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.
4. Using distance from intersection point
Observation: The total number of nodes in the first list + distance of the head of the second list from the intersection point = The total number of nodes in the second list + distance of the head of the first list from the intersection point.
The idea is to take two pointers, x and y, initially pointing to the head of the first and second lists. Then advance both pointers at the same pace until they meet at a common node. When x reaches its end, redirect it to the head of the second list. When y reaches its end, turn it to the head of the first list. The node where x meets y is the intersection node.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#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; } |
Output:
The intersection point is 4
Java
|
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
// 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."); } } } |
Output:
The intersection point is 4
Python
|
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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
# 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.') |
Output:
The intersection point is 4
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.
Also See:
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)