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.

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.

/*
Definition for singly-linked list.

public class Node {
  int val;
  Node next;
  Node(int x) { val = x; }
}
*/

public class Solution {
  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
  
  }
}

This problem is selected from LeetCode.

Solution

Solution1: first find the length of the two linked list and get the length difference. Then traverse the longer linked list and
move length difference steps first. Then traverse the two lists at the same time until a common node is found.

public class Solution {
  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    
    if(headA==null||headB==null) 
      return null;
      
    int lenA=0;
    int lenB=0;
    
    // get the length of A and B
    for(ListNode A=headA;A!=null;A=A.next){
        lenA++;
    }
    for(ListNode B=headB;B!=null;B=B.next){
        lenB++;
    }
    
    // move the head of the longer
    // list the length difference steps
    while(lenA>lenB){
        headA=headA.next;
        lenA--;
    }
    while(lenB>lenA){
        headB=headB.next;
        lenB--;
    }
    
    // move headA and headB together
    // until a common node is found.
    while(headA!=headB){
        headA=headA.next;
        headB=headB.next;
    }
    
    // headA and headB now 
    // point to the same node
    // or both are null
    
    return headA;
  }
}

The solution needs O(m+n) time and O(1) space.

Solution2: For both lists, connect the end of one list to the head of the other (like the digit 8). Then use two pointers to scan
both lists. For each list once it reaches the end, continue scanning the other list. Once the two runner equal to each other, return the position

public class Solution {
  public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if( null==headA || null==headB ) return null;
  
    ListNode curA = headA, curB = headB;
    while( curA!=curB){
      curA = curA==null?headB:curA.next;
      curB = curB==null?headA:curB.next;
    }
    return curA;
  }
}

Same to solution1, the solution needs O(m+n) time and O(1) space.

RelatedPost