List: Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return null.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) return null; int lengthA = length(headA); int lengthB = length(headB); int diff = Math.abs(lengthA - lengthB); while(diff>0){ if(lengthA > lengthB) headA = headA.next; else{ headB = headB.next; } diff--; } while(headA != null && headB!=null){ if(headA.val == headB.val) return headA; else{ headA = headA.next; headB = headB.next; } } return null; } public int length(ListNode node){ int count =0 ; if(node == null) return count; while(node!= null){ count++; node = node.next; } return count; } }

public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { int len1 = len(headA); int len2 = len(headB); while(len1 > len2){ len1--; headA = headA.next; } while(len2 > len1){ len2--; headB = headB.next; } while(headA != headB){ headA = headA.next; headB = headB.next; } return headA; } public int len(ListNode node){ int len = 0; while(node != null){ len++; node = node.next; } return len; } }