Intersection of Two Linked Lists

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

You may view the full question here.

(Highly recommend you to check it out. NOTE: It’s important that not just the values of the nodes match, but the addresses of the nodes need to match to qualify as an intersection.)

Approach 1: This is a pretty simple approach.

The main issue we face is that we are unaware of the indices from which the intersection begins in the two lists. We understand that the intersection lies on the last ’n’ nodes. And we leverage this knowledge to our benefit and start comparing the nodes from the tail.

Pictorial representation of Approach 1

//Approach 1:
//Runtime: 2ms
//Memory usage: 38.9MB
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    private class Node {
        ListNode ln;
        Node prev;
        Node(ListNode ln){
            this.ln = ln;
            prev = null;
        }
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode currA = headA;
        Node revA = null;
        while(currA!=null){
            Node n = new Node(currA);
            n.prev = revA;
            revA = n;
            
            currA = currA.next;
        }
        
        ListNode currB = headB;
        Node revB = null;
        while(currB!=null){
            Node n = new Node(currB);
            n.prev = revB;
            revB = n;
            
            currB = currB.next;
        }
        
        ListNode result = null;
        while(revA!=null && revB!=null && revA.ln==revB.ln){
            result = revA.ln;
            
            revA = revA.prev;
            revB = revB.prev;
        }
        
        return result;
    }
}

The redundant part in this approach is that we are reading through the intersected nodes twice(once when we reverse, next when we are in the pursuit of the starting point of the intersection), while we actually just need the node where the intersection starts.

Approach 2: We could use our trusty (Hash)Map to store all the nodes on one list and checking if we find a match while traversing through the second list. But, the penalty paid in terms of run-time in this approach is 7x the previous approach due to an expensive add() operation.

Approach 3: The next approach was with some help from the wonderful discussions here.

Here —

• We compare from the start to end
• But, we make sure to first eliminate the plausible extra nodes in the beginning of the longer list
• We start the comparison after skipping the extra nodes. As soon as a match is found we return it

Pictorial representation of Approach 2

//Approach 2:
//Runtime: 1ms
//Memory usage: 39.4MB
/**
 * 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 = length(headA);
        int lenB = length(headB);
        
        ListNode currA = headA;
        ListNode currB = headB;
        
        if(lenA<lenB){
            currB = move(currB, lenB-lenA);
        } else {
            currA = move(currA, lenA-lenB);
        }
        
        while(currA!=null && currB!=null){
            if(currA==currB){
                return currA;
            }
            currA = currA.next;
            currB = currB.next;
        }
        return null;
    }
    
    private ListNode move(ListNode list, int count){
        while(count-->0){
            list=list.next;
        }
        return list;
    }
    
    private int length(ListNode head){
        int count = 0;
        ListNode curr = head;
        while(curr!=null){
            count++;
            curr=curr.next;
        }
        return count;
    }
}

Find more posts here.

Cheers & Chao!