Teaching Kids Programming – Algorithms to Compute the Intersection of Two Linked Lists

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given Two Linked Lists, compute the Intersection Node:

For example:

1 - 2 - 3 - 4 - 5
        |
6 - 7 - 8

The intersection node is 3.

Using Hash Set to Compute the Intersection of Two Linked List

We can leverage the hash set to remember all the nodes of a linked list, then, by traversing another linked list, if a node has appeared in the hash set, it must be the intersection.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        d = set()
        while headA:
            d.add(headA)
            headA = headA.next
        while headB:
            if headB in d:
                return headB
            headB = headB.next
        return None

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        d = set()
        while headA:
            d.add(headA)
            headA = headA.next
        while headB:
            if headB in d:
                return headB
            headB = headB.next
        return None

The time complexity is O(N+M) and the space complexity is O(Max(N, M)) where N and M is the number of the nodes in the two linked list respectively.

Algorithm of O(1) Constant to Get the Intersection Node of the two Linked Lists

We let two pointers start at head of each linked list, then once it reaches the end, it starts from another. Let’s define the length of the first linked list is L1+C and second linked list is L2+C where C is the common part. Once pointer A traverse to the end, it will traverse till the intersection part: L1+C+L2 and same for second pointer which will traverse L2+C+L1, so they will meet at the intersection part.

1
2
3
4
5
6
7
8
9
10
11
12
13

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
 
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        a, b = headA, headB
        while a != b:
            a = a.next if a else headB
            b = b.next if b else headA
        return a

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        a, b = headA, headB
        while a != b:
            a = a.next if a else headB
            b = b.next if b else headA
        return a

The time complexity is O(M+N) and the space complexity is O(1) constant. However as this algorithm let two pointers traverse more than one pass, so it may be slower than the above O(M+N) solution.

–EOF (The Ultimate Computing & Technology Blog) —