0160 Intersection of Two Linked List

0160 Intersection of Two Linked List#

Problem#

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

Examples#

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

Example 2:

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Constraints#

The number of nodes of listA is in the m.
The number of nodes of listB is in the n.
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA < m
0 <= skipB < n
intersectVal is 0 if listA and listB do not intersect.
intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

Analysis#

Method 1: hash map

  • create an empty hash set

  • traverse the first linked list, and store the visited node in the hash set

  • traverse the second linked list. Check if it is present in the hash set.

This method might requires all nodes have unique value. The example 2 probably will not pass.

Merhod 2: two pointer method

  • if two pointers p1 and p2 walks normally on two lists, they cannot meet each other at the intersection. Then how can the two pointers can meet at the intersection?

  • we can link these two lists together

    • traverse list 1, and then traverse list 2

    • traverse list 2, and then traverse list 1

    • if there is an intersection, the two pointers will have the same node

  • The idea can be described as the following figure.

figure 1 figure 2

Method 3: two pointer method

  • in cycle detection, we have algorithms to detect the cycle entrance, which is similar to intersection dectection

  • we can formulate a cycle out of these two intersected lists

    • make list 1 a circular list by connecting its last node to its first node -> make a cycle

    • detect the cycle entrance starting from the head of list 2

    • remove the circular list

Solution#

class Node():
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build(A):
    dummy = Node()

    if not A:
        return dummy.next
    
    prev = dummy
    for a in A:
        cur = Node(a)
        prev.next = cur 
        prev = cur
    
    return dummy.next 

def linkedListToList(head):
    res = []
    while head:
        res.append(head.val)
        head = head.next
    return res

# Method 2: 
# Note current implementation will return None because when we build the linked list, the address are different for the nodes that are even intersected.
# The code will run on leetcode test
def intersectionList(headA, headB):
    p1, p2 = headA, headB 
    while p1 != p2:
        if p1 == None:
            p1 = headB
        else:
            p1 = p1.next 
        if p2 == None:
            p2 = headA 
        else:
            p2 = p2.next
    
    if not p1:
        return None
    
    return p1

# Test
headA = build([[4,1,8,4,5]])
headB = build([[5,6,1,8,4,5]])
print(intersectionList(headA, headB))

None

# Method 3:
def intersectionList(headA, headB):
    # formulate a cycle
    tailA = headA
    while tailA.next:
        tailA = tailA.next
    tailA.next = headA 

    # detect the cycle entrance and return
    slow, fast = headB, headB 
    while fast and fast.next:
        slow = slow.next 
        fast = fast.next.next
        if slow == fast:
            break
    
    # find entrance if there is cycle
    if fast and fast.next:
        slow = headB
        
        while slow != fast:
            slow = slow.next
            fast = fast.next
        
        return slow
    
    # return None if no cycle
    else:
        return None
Contents