Intersection of Two Linked Lists

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

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.

 

We can solve this question by 2 steps: 
1. Before traversing the linked list, compare the length of each linked list, and adjust the pointer of the longer one, so that there are same number of nodes left after the pointers.  
2. Traverse the linked lists together. Each time compare whether the address of two nodes from List A and List B are the same. 

 

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = getLength(headA);
        int lenB = getLength(headB);        
        int lenDiff = 0; 
        
        ListNode curA = headA; 
        ListNode curB = headB; 
        if (lenA > lenB) {
            lenDiff = lenA - lenB; 
            while (lenDiff > 0 ) {
                curA = curA.next; 
                lenDiff--; 
            }
        } else {
            lenDiff = lenB - lenA; 
            while (lenDiff > 0) {
                curB = curB.next; 
                lenDiff--; 
            }
        }
        
        
        /*Only after adjusting the starting point, can we traverse two linked list together */
        while (curA != null) {
            if (curA == curB) {
                return curA; 
            }
            
            curA = curA.next; 
            curB = curB.next; 
        }
        return null; 
    }
    
    public int getLength (ListNode head) {
        ListNode cur = head; 
        int len = 0; 
        
        if (head == null) 
            return 0; 
        
        while (cur != null) {
            cur = cur.next; 
            len++; 
        }
        
        return len; 
    }

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s