LeetCode Intersection of Two Linked Lists: 4 Different Methods

Overview

LeetCode Intersection of Two Linked Lists could be solved in 4 different ways: reduce to the cycle detection, two pointers, hashing, brute force.

LeetCode Intersection of Two Linked Lists

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

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

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.

Solution Analysis: 4 Different Methods

1) brute force: for each node from list A, we test if this node is in list B by linear scanning list B. The time complexity would be O(mn) and space cost is constant O(1)

2) hashing: the test of whether some node in A is in B or not could be done in O(1) time by keeping the address of each node in B in a hash table, so test whether an address of another node is in B or not could now be done in O(1) time. First O(n) time to insert all the node address of list B into hash table , and then linear scan A (length is m) to do the test. The time complexity is O(m + n) while the space cost is O(n).

3) this problem could be reduced into the linked list cycle problem where we need to find the start node of the cycle in a singly linked list as in “LeetCode Linked List Cycle II: The Mathematical Fact“. So the first step would be linear scan linked list A and make the tail node point to the head of A and keep the tail node information for later recovery. Next this problem becomes to find the start node of the cycle in linked list B which could be solved in O(m+n) time and O(1) space as in  ”LeetCode Linked List Cycle II: The Mathematical Fact“. Finally, we need to recover list A as this problem requires that the original structure cannot be changed. This is a good example to solve the problem by chaning it into some old or familar problem to us. But the cycle dection is actually more complicated, so we are making it more difficult if we do not know the old problem and this intersection problem has an easier approach.

4) optimal solution: the key fact to tackle this problem is that if two linked list are of equal length, then the could be scanned in the same pace, and the intersection would be found when they encounter with each other. So we can get the length of both list A and B, and let d be the difference, we move the current pointer of the longer list d nodes ahead of the shorter one, now the current pointers to A and B are at the same pace, we move these two one step by step until we find the same node and this is the one we return. The following code is accepted by LeetCode OJ to pass this Intersection of Two Linked Lists problem:

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    if (NULL == headA || NULL == headB) return NULL;
    int lenA = getLength(headA);
    int lenB = getLength(headB);
    if (lenB > lenA) swap(headA, headB), swap(lenA, lenB);
    int d = lenA - lenB;
    while (d--) headA = headA->next;
    while (headA) {
        if (headA == headB) return headA;
        headA = headA->next;
        headB = headB->next;
    }
    return NULL;
}

Summary

LeetCode Intersection of Two Linked Lists could be solved in 4 different ways: reduce to the cycle detection, two pointers, hashing, brute force.

Written on December 8, 2014