Start learning free

LESSON 304 OF 414 · LINKED LISTS

Intersection of Two Linked Lists in Scala: O(m + n) Time, O(1) Space

Practice O(n) Read the full explanation

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:



The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

  • intersectVal - The value of the node where the intersection occurs. This is 0 if there is no intersected node.
  • listA - The first linked list.
  • listB - The second linked list.
  • skipA - The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.
  • skipB - The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.

 

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.

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 m.
  • The number of nodes of listB is n.
  • 1 <= m, n <= 3 * 104
  • The value of each node is between 1 and 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.

 

Follow up: Could you write a solution that runs in O(m + n) time and use only O(1) memory?
STEP 1 OF 17
    Ctrl + Enter to check

    SCALA · LINKED LISTS

    Intersection Of Two Linked Lists in Scala, explained

    Problem overview

    The method getIntersectionNode receives the heads of two singly linked lists, headA and headB. The lists may merge into one shared tail. If they do, the method returns the first node that belongs to both lists. If they never meet, it returns null. The lists must keep their original structure, and the input has no cycles.

    The word "intersect" means the same node object, not just equal values. In the first example, list A reads [4, 1, 8, 4, 5] and list B reads [5, 6, 1, 8, 4, 5]. Both contain a 1 before the 8, but those are two separate nodes. The lists share the tail that starts at the node holding 8, so the answer is that node. In the third example, [2, 6, 4] and [1, 5] share nothing, so the answer is null.

    The follow-up asks for O(m + n) time and O(1) memory, where m and n are the lengths of the lists.

    Approach: align the starting points

    Storing every node of A in a set and checking B against it takes O(m) extra memory, which the follow-up rules out. Comparing every node of A with every node of B takes O(m * n) time.

    The better idea uses one fact: once the lists meet, they are the same list from there to the end. So the part after the intersection has the same length in both. Any extra length is in the part before it, and only the longer list can have more of it.

    Suppose A has 5 nodes and B has 6. Skip the first node of B. Now both remaining lists have 5 nodes, and any shared tail sits at the same distance from the end in both. Walk one step at a time with a pointer in each list. They are on the same node as soon as they reach the intersection, and if the lists don't intersect, they both reach null together. In both cases the pointers compare equal, so one loop handles both outcomes.

    Step by step

    1. Measure list A with a helper, val sizeA = size(headA). The helper gets written at the end.
    2. Measure list B the same way, val sizeB = size(headB).
    3. Create two walkers, var nA = headA and var nB = headB. The parameters can't be reassigned, and the walkers will move.
    4. Compare the lengths with if (sizeA < sizeB). Whichever list is longer needs to skip its extra nodes.
    5. Advance B's walker by sizeB - sizeA using the second helper, moveNode. The helper returns the node it stopped on, so the result must be assigned back: nB = moveNode(nB, sizeB - sizeA).
    6. Otherwise advance A's walker by sizeA - sizeB. When the lengths are equal, that distance is 0 and nothing moves.
    7. Walk together with while (nA ne nB). This compares references, not contents.
    8. Advance both walkers one step inside the loop.
    9. Return nA as the last expression. It is the intersection node, or null when the walkers ran off the ends together.
    10. Write size. Copy head into var node and start a var count = 0.
    11. Loop while node != null.
    12. Count and move with count += 1 and node = node.next.
    13. Yield count as the method's value.
    14. Write moveNode. Copy both parameters into mutable locals, var n = node and var kk = k.
    15. Loop while kk > 0.
    16. Step forward with n = n.next and kk -= 1.
    17. Yield n, the node where the walk ended.

    The solution in Scala

    class Solution {
    def getIntersectionNode(headA: ListNode, headB: ListNode): ListNode = {
        val sizeA = size(headA)
        val sizeB = size(headB)
        var nA = headA
        var nB = headB
        if (sizeA < sizeB) {
            nB = moveNode(nB, sizeB - sizeA)
        } else {
            nA = moveNode(nA, sizeA - sizeB)
        }
        while (nA ne nB) {
            nA = nA.next
            nB = nB.next
        }
        nA
    }

    def size(head: ListNode): Int = {
        var count = 0
        var node = head
        while (node != null) {
            count += 1
            node = node.next
        }
        count
    }

    def moveNode(node: ListNode, k: Int): ListNode = {
        var n = node
        var kk = k
        while (kk > 0) {
            n = n.next
            kk -= 1
        }
        n
    }
}

    The Scala details worth knowing:

    • ne and eq. These operators compare references. a ne b is true when a and b are different objects. == calls equals, which a class may override to compare contents (case classes do), so for "is this the same node?" the reference operators are the safe choice. Both operators accept null on either side, which is why the loop ends when both walkers reach null.
    • The last expression is the result. The methods end with nA, count and n and need no return. An if/else used as a statement, as here, simply runs one of its branches.
    • Parameters are immutable. That is why size and moveNode copy their arguments into var locals before changing them.
    • Method order doesn't matter. Inside a class, getIntersectionNode can call size and moveNode even though they are defined below it.
    • Return types. The methods declare ListNode and Int, and nA may be null at the end, which is a legal value for ListNode here.

    Complexity

    Time: O(m + n). Measuring the lists costs m + n steps. Skipping the extra nodes costs at most |m - n| steps, and the final walk takes at most min(m, n) steps. Everything adds up to a small multiple of m + n.

    Space: O(1). Only a few integers and two node references are stored, and the lists are never modified.

    Edge cases and common mistakes

    • No intersection. After alignment, the walkers step through the rest of their lists and both become null on the same step. Then nA ne nB is false and the method returns null.
    • Equal lengths. The skip is 0 and the loop starts right away. If the heads are the same node, the loop doesn't run and that head is returned.
    • The intersection is the head of the shorter list. If B is itself the shared tail, A skips its extra nodes and both walkers start on the shared head, so the loop body never runs and that node is returned.
    • Comparing values instead of nodes. Two different nodes can both hold 1, or even the same values all the way down. Only reference comparison identifies a shared node, which is why the loop uses ne.
    • Dropping the assignment. Writing moveNode(nB, sizeB - sizeA) without nB = does nothing useful: the helper returns a node but can't change which node nB refers to.
    • Skipping the wrong list. Advancing the shorter list makes the walkers misaligned, so they would run past the intersection and never compare equal at the right node.
    • Breaking the lists. The code never changes a next link, so the structure is preserved as the statement requires.

    Testing

    • A = [4, 1, 8, 4, 5], B = [5, 6, 1, 8, 4, 5], sharing the tail from the node holding 8, returns that node (value 8).
    • A = [1, 9, 1, 2, 4], B = [3, 2, 4], sharing the tail from the node holding 2, returns that node (value 2).
    • A = [2, 6, 4], B = [1, 5], with no shared node, returns null.
    • The same list passed as both A and B returns its head.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free