Ac solution code


  • 15

    Procedure:

    1. When pointer X in shorter list reaches the end, pointer Y in the longer list will have len(longer) - len(shorter) left. Put pointer X to the head of the longer list, then when Y reaches its end, X already traveled len(longer)-len(shorter). Then put Y to the head of shorter list.

    2. Now X and Y have the same distance to the end:
      1). If has intersection, intersection is the first node where X = Y
      2). If no intersection, termination case is X = Y = null, where they reach end together (as X, Y have the same distance to end)

    Runtime complexity = O(m + n)

    m = len(longer), n = len(shorter):

    step 1: uses m time
    step 2: uses n time
    

    .

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

  • 0
    J

    nice solution!


  • 1
    D

    Won't this go in infinite loop if there is no cycle?


  • 0
    J

    super nice solution!


  • 0
    J

    Yes, it seems it will contains the loop.


  • 0
    L

    no, if there is no cycle, then the 2 pointers will reach the nullptr at the same time.


  • 0
    H

    No. You can view two linkedlist connect at the null node in the end of two list. Two pointer run through same distance, so they will definite merge at that point.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.