Start learning free

LESSON 274 OF 338 · LINKED LISTS

Intersection of Two Linked Lists in Go: 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 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.

 

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

    GO · LINKED LISTS

    Intersection Of Two Linked Lists in Go, explained

    Problem overview

    The function getIntersectionNode receives the heads of two singly linked lists, headA and headB. The lists may merge into a shared tail: from some node on, both lists continue through the very same nodes. The function must return that first shared node, or nil if the lists never meet. The lists have no cycles, and they must be left unchanged.

    In the first example, list A is 4, 1, 8, 4, 5 and list B is 5, 6, 1, 8, 4, 5. They share the tail 8, 4, 5, so the answer is the node holding 8. It is the same node, not just a node with an equal value: A reaches it after 2 nodes and B after 3. The second 1 in B is a different node from the 1 in A, even though the values match.

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

    Approach: align the starting points

    Two easy solutions exist. Comparing every node of A with every node of B takes O(m * n). Storing the nodes of A in a set and then checking each node of B takes O(m + n) time but O(m) memory. This lesson reaches O(1) memory with a different idea.

    If the lists intersect, everything after the meeting point is shared, so that part has the same length in both lists. The two lists can only differ in length before the meeting point. If the longer list's pointer first skips its extra nodes, both pointers are then the same distance from the end. Moving them forward together, one step at a time, makes them arrive at the intersection at the same moment. If the lists never meet, both pointers reach nil together, and nil == nil ends the loop.

    On the first example, sizeA is 5 and sizeB is 6, so B's pointer skips 1 node and lands on B's second node (the value 6). Both pointers then have 4 nodes to go. They step together: 4 and 6, then 1 and 1 (two different nodes), then 8 and 8, the same node. The loop stops and the function returns it.

    Step by step

    1. Compute both lengths with a helper: sizeA := size(headA) and sizeB := size(headB). The helper is written afterwards.
    2. Create walking pointers nA := headA and nB := headB, so the parameters stay untouched.
    3. Find the longer list. If sizeA < sizeB, list B is longer.
    4. Skip B's extra nodes: nB = moveNode(nB, sizeB-sizeA). The helper returns the node it stopped on, so the result must be assigned back. The function receives a copy of the pointer, which it can't change in the caller.
    5. Otherwise A is at least as long, and nA = moveNode(nA, sizeA-sizeB) skips A's extra nodes. When the lengths are equal, the distance is 0 and nothing moves.
    6. Loop while nA != nB. Go has no while, so this is a for with only a condition. Comparing pointers with != asks whether they refer to different nodes, not whether the values differ.
    7. Advance both with nA = nA.Next and nB = nB.Next.
    8. Return nA. It is the intersection node, or nil when the lists don't meet.
    9. Write size: a counter starts at 0, and a for head != nil loop increments it and advances head. The parameter is a copy, so walking it doesn't disturb the caller.
    10. Write moveNode: while k > 0, step node = node.Next and decrement k, then return node.

    The solution in Go

    func getIntersectionNode(headA, headB *ListNode) *ListNode {
	sizeA := size(headA)
	sizeB := size(headB)
	nA := headA
	nB := headB
	if sizeA < sizeB {
		nB = moveNode(nB, sizeB-sizeA)
	} else {
		nA = moveNode(nA, sizeA-sizeB)
	}
	for nA != nB {
		nA = nA.Next
		nB = nB.Next
	}
	return nA
}
func size(head *ListNode) int {
	count := 0
	for head != nil {
		count++
		head = head.Next
	}
	return count
}
func moveNode(node *ListNode, k int) *ListNode {
	for k > 0 {
		node = node.Next
		k--
	}
	return node
}

    Go details worth knowing:

    • Pointer comparison is identity. For two *ListNode values, == is true only if both hold the same address. Two separate nodes with equal Val are not equal as pointers. That is exactly the question this problem asks.
    • Parameters are copies. In size, the line head = head.Next changes only the local copy of the pointer. In moveNode, the same is true of node and k, which is why the caller must use the return value.
    • Helpers can follow their callers. Go resolves package-level functions regardless of the order of declaration, so size and moveNode may be written below the function that calls them.

    Complexity

    Time: O(m + n). size walks each list once, moveNode walks at most the longer list once, and the final loop takes at most as many steps as the shorter list has nodes.

    Space: O(1). Four pointers and a few integers, regardless of the list sizes. Nothing is allocated, and the lists are not modified.

    Edge cases and common mistakes

    • No intersection. For [2, 6, 4] and [1, 5] the pointers walk together until both are nil, the loop condition becomes false, and the function returns nil. The loop never dereferences a nil pointer, because both pointers become nil on the same step.
    • Equal values, different nodes. Two separately built lists [1, 2] and [1, 2] don't intersect, and the function returns nil. Comparing .Val instead of the pointers would wrongly report an intersection.
    • Intersection at the head. If both heads are the same node, the lengths are equal, nothing is skipped, and the loop doesn't run: it returns headA immediately.
    • Skipping the wrong amount. If the pointers start at different distances from the end, they never meet at the shared node. One of them reaches nil first, and the next nA.Next or nB.Next panics with a nil pointer dereference.
    • Modifying the lists. The statement requires the original structure to remain. This solution only reads Next.

    Testing

    • A = 4, 1, 8, 4, 5 and B = 5, 6, 1, 8, 4, 5, sharing the tail that starts at 8: returns the shared node with value 8.
    • A = [2, 6, 4] and B = [1, 5], no shared nodes: returns nil.
    • The same list passed as both arguments: returns that list's head.
    • Two separately built lists with equal values: returns nil.
    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free