Brute force approach:
Time complexity: O(N+M) where N and M are length of two LinkedLists given.
Intuition
Find length of both the nodes and get the length difference
Travel ahead in the longest list by length difference of both the lists, by this both the lists will start from the same length.
return when same nodes are encountered.
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
int lenA = findLength(headA);
int lenB = findLength(headB);
ListNode A = headA;
ListNode B = headB;
int diff = Math.abs(lenA–lenB);
if(lenA > lenB){
A = travelAhead(A,diff);
}
else B = travelAhead(B,diff);
return findIntegersection(A,B);
}
public ListNode findIntegersection(ListNode a, ListNode b){
while(a!=null && b!=null){
if(a.equals(b)) return a;
a= a.next;
b= b.next;
}
return null;
}
public ListNode travelAhead(ListNode head, int diff){
while(diff–>0){
head = head.next;
}
return head;
}
public int findLength(ListNode head){
int count = 0;
while(head!=null){
head = head.next;
count++;
}
return count;
}
}
