Given two linked lists of size N and M consisting of positive value nodes, having a common intersection point, the task is to find the intersection point of the two linked lists where they merge.
Examples:
Input: L1: 3 ? 6 ? 9 ? 15 ? 30, L2: 10 ? 15 ? 30
Output: 15
Explanation:
From the above image, the intersection point of the two linked lists is 15.
Input: L1: 1 ? 2 ? 3, L2: 4 ? 5 ? 1 ? 2 ? 3
Output: 1
Approach: The idea is to traverse the first linked list and multiply the value of each node by -1 thus making them negative. Then, traverse the second linked list and print the value of the first node having a negative value. Follow the steps below to solve the problem:
- Traverse the first linked list L1 and multiply the value of each node by -1.
- Now, traverse the second linked list L2 and if there exists any node with negative values then print the absolute value of the node’s value as the resultant intersection of the linked list and break out of the loop.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Structure of a node // of a Linked List class Node { public: int data; Node* next; // Constructor Node(int x) { data = x; next = NULL; } }; // Function to find the intersection // point of the two Linked Lists Node* intersectingNode(Node* headA, Node* headB) { // Traverse the first linked list // and multiply all values by -1 Node* a = headA; while (a) { // Update a -> data a->data *= -1; // Update a a = a->next; } // Traverse the second Linked List // and find the value of the first // node having negative value Node* b = headB; while (b) { // Intersection point if (b->data < 0) break; // Update b b = b->next; } return b; } // Function to create linked lists void formLinkList(Node*& head1, Node*& head2) { // Linked List L1 head1 = new Node(3); head1->next = new Node(6); head1->next->next = new Node(9); head1->next->next->next = new Node(15); head1->next->next->next->next = new Node(30); // Linked List L2 head2 = new Node(10); head2->next = head1->next->next->next; return; } // Driver Code int main() { Node* head1; Node* head2; formLinkList(head1, head2); cout << abs(intersectingNode(head1, head2) ->data); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG{ static Node head1 = null; static Node head2 = null; // Structure of a node // of a Linked List static class Node { int data; Node next; // Constructor Node(int x) { data = x; next = null; } } // Function to find the intersection // point of the two Linked Lists static Node intersectingNode(Node headA, Node headB) { // Traverse the first linked list // and multiply all values by -1 Node a = headA; while (a != null) { // Update a -> data a.data *= -1; // Update a a = a.next; } // Traverse the second Linked List // and find the value of the first // node having negative value Node b = headB; while (b != null) { // Intersection point if (b.data < 0) break; // Update b b = b.next; } return b; } // Function to create linked lists static void formLinkList() { // Linked List L1 head1 = new Node(3); head1.next = new Node(6); head1.next.next = new Node(9); head1.next.next.next = new Node(15); head1.next.next.next.next = new Node(30); // Linked List L2 head2 = new Node(10); head2.next = head1.next.next.next; return; } // Driver Code public static void main(String[] args) { formLinkList(); System.out.println(Math.abs( intersectingNode(head1, head2).data)); } } // This code is contributed by Dharanendra L V. |
Python3
# Python3 program for the above approach # Structure of a node # of a Linked List class Node: def __init__(self, d): self.data = d self.next = None # Function to find the intersection # point of the two Linked Lists def intersectingNode(headA, headB): # Traverse the first linked list # and multiply all values by -1 a = headA while (a): # Update a . data a.data *= -1 # Update a a = a.next # Traverse the second Linked List # and find the value of the first # node having negative value b = headB while (b): # Intersection point if (b.data < 0): break # Update b b = b.next return b # Function to create linked lists def formLinkList(head1, head2): # Linked List L1 head1 = Node(3) head1.next = Node(6) head1.next.next = Node(9) head1.next.next.next = Node(15) head1.next.next.next.next = Node(30) # Linked List L2 head2 = Node(10) head2.next = head1.next.next.next return head1, head2 # Driver Code if __name__ == '__main__': head1, head2 = formLinkList(None, None) print(abs(intersectingNode(head1, head2).data)) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; public class Node { public int data; public Node next; // Constructor public Node(int x) { data = x; next = null; } } public class GFG{ static Node head1 = null; static Node head2 = null; // Function to find the intersection // point of the two Linked Lists static Node intersectingNode(Node headA, Node headB) { // Traverse the first linked list // and multiply all values by -1 Node a = headA; while (a != null) { // Update a -> data a.data *= -1; // Update a a = a.next; } // Traverse the second Linked List // and find the value of the first // node having negative value Node b = headB; while (b != null) { // Intersection point if (b.data < 0) break; // Update b b = b.next; } return b; } // Function to create linked lists static void formLinkList() { // Linked List L1 head1 = new Node(3); head1.next = new Node(6); head1.next.next = new Node(9); head1.next.next.next = new Node(15); head1.next.next.next.next = new Node(30); // Linked List L2 head2 = new Node(10); head2.next = head1.next.next.next; return; } // Driver Code static public void Main () { formLinkList(); Console.WriteLine(Math.Abs( intersectingNode(head1, head2).data)); } } // This code is contributed by unknown2108. |
Javascript
<script> // JavaScript program for the above approach let head1 = null; let head2 = null; // Structure of a node // of a Linked List class Node { constructor(x) { this.data=x; this.next=null; } } // Function to find the intersection // point of the two Linked Lists function intersectingNode(headA,headB) { // Traverse the first linked list // and multiply all values by -1 let a = headA; while (a != null) { // Update a -> data a.data *= -1; // Update a a = a.next; } // Traverse the second Linked List // and find the value of the first // node having negative value let b = headB; while (b != null) { // Intersection point if (b.data < 0) break; // Update b b = b.next; } return b; } // Function to create linked lists function formLinkList() { // Linked List L1 head1 = new Node(3); head1.next = new Node(6); head1.next.next = new Node(9); head1.next.next.next = new Node(15); head1.next.next.next.next = new Node(30); // Linked List L2 head2 = new Node(10); head2.next = head1.next.next.next; return; } // Driver Code formLinkList(); document.write(Math.abs( intersectingNode(head1, head2).data)); // This code is contributed by patel2127 </script> |
Output:
15
Time Complexity: O(N + M)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
