Solving Intersection of Two Linked Lists in Go: Step-by-Step Guide

Introduction to the Intersection of Two Linked Lists Problem

The "Intersection of Two Linked Lists" is a classic algorithmic problem frequently encountered in coding interviews and competitive programming. Given the heads of two singly linked lists, your task is to determine the node at which they intersect. If the two lists have no intersection, you should return nil.

What makes this problem interesting is the constraint that the two lists may have different lengths before the intersection point. The intersection itself is defined by reference equality — that is, the two lists share the exact same node in memory, not merely nodes with identical values. Once the lists intersect, every subsequent node is shared between them.

Why This Problem Matters

Understanding how to solve this problem sharpens your grasp of pointer manipulation, list traversal, and algorithmic optimization. It also teaches you how to handle structural differences between data structures elegantly. In real-world systems, linked lists are used in memory allocators, hash table implementations (chaining), and LRU caches — scenarios where detecting shared substructures can be crucial for correctness and performance.

Defining the Linked List Structure in Go

Before tackling the algorithm, we need a clear definition of a singly linked list node in Go. We will use a simple struct with an integer value and a pointer to the next node.

package main

import "fmt"

// ListNode represents a node in a singly linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

// helper to build a linked list from a slice
func buildList(values []int) *ListNode {
    dummy := &ListNode{}
    current := dummy
    for _, v := range values {
        current.Next = &ListNode{Val: v}
        current = current.Next
    }
    return dummy.Next
}

This structure gives us a foundation for constructing test cases and verifying our solution.

Understanding the Problem With an Example

Consider two linked lists:

List A: 4 -> 1 -> 8 -> 4 -> 5
List B: 5 -> 6 -> 1 -> 8 -> 4 -> 5

If the node with value 8 is the same node in memory for both lists, then the intersection begins at that node. The lists share the tail 8 -> 4 -> 5. The challenge is to find that shared node efficiently.

A naive approach would be to compare every node of list A with every node of list B, resulting in O(m * n) time complexity. We can do much better.

Approach 1: Length Difference Method

The key insight is that if both lists had the same length, we could traverse them in lockstep and compare nodes one by one. The only obstacle is the length difference before the intersection. By calculating the length of each list first, we can advance the pointer of the longer list by the difference, effectively aligning both lists at the same distance from the intersection.

Step-by-Step Algorithm

• Traverse list A to compute its length, lenA.
• Traverse list B to compute its length, lenB.
• Compute the absolute difference diff = abs(lenA - lenB).
• Advance the pointer of the longer list by diff steps.
• Traverse both lists simultaneously, comparing nodes by reference.
• Return the first matching node, or nil if none is found.

Implementation in Go

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }

    // Step 1: compute lengths
    lenA, lenB := 0, 0
    for node := headA; node != nil; node = node.Next {
        lenA++
    }
    for node := headB; node != nil; node = node.Next {
        lenB++
    }

    // Step 2: align starting points
    ptrA, ptrB := headA, headB
    if lenA > lenB {
        for i := 0; i < lenA-lenB; i++ {
            ptrA = ptrA.Next
        }
    } else {
        for i := 0; i < lenB-lenA; i++ {
            ptrB = ptrB.Next
        }
    }

    // Step 3: traverse together
    for ptrA != ptrB {
        ptrA = ptrA.Next
        ptrB = ptrB.Next
    }

    return ptrA // will be nil if no intersection
}

This solution runs in O(m + n) time and uses O(1) extra space, which is optimal for this problem.

Approach 2: Two-Pointer Technique

There is an elegant alternative that avoids explicitly computing lengths. The idea is to use two pointers, each starting at the head of one list. When a pointer reaches the end of its list, redirect it to the head of the other list. After at most two passes, both pointers will be aligned at the intersection node (or both will be nil if there is no intersection).

Why This Works

Suppose list A has length a + c and list B has length b + c, where c is the length of the shared tail. Pointer A traverses a + c nodes, then switches to list B and traverses b more nodes — a total of a + c + b steps. Pointer B traverses b + c nodes, then switches to list A and traverses a more nodes — also b + c + a steps. Since both pointers travel the same total distance, they meet at the intersection node.

Implementation in Go

func getIntersectionNodeTwoPointer(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }

    ptrA, ptrB := headA, headB

    for ptrA != ptrB {
        if ptrA == nil {
            ptrA = headB
        } else {
            ptrA = ptrA.Next
        }

        if ptrB == nil {
            ptrB = headA
        } else {
            ptrB = ptrB.Next
        }
    }

    return ptrA
}

This version is more concise and equally efficient. The redirect-on-nil trick elegantly handles the length difference without an explicit calculation.

Building a Test Case

To verify our solution, we need to construct two lists that actually share a tail. We do this by creating the shared portion once and attaching it to both lists.

func main() {
    // shared tail: 8 -> 4 -> 5
    shared := &ListNode{Val: 8}
    shared.Next = &ListNode{Val: 4}
    shared.Next.Next = &ListNode{Val: 5}

    // list A: 4 -> 1 -> [shared]
    headA := &ListNode{Val: 4}
    headA.Next = &ListNode{Val: 1}
    headA.Next.Next = shared

    // list B: 5 -> 6 -> 1 -> [shared]
    headB := &ListNode{Val: 5}
    headB.Next = &ListNode{Val: 6}
    headB.Next.Next = &ListNode{Val: 1}
    headB.Next.Next.Next = shared

    result := getIntersectionNode(headA, headB)
    if result != nil {
        fmt.Printf("Intersection at node with value: %d\n", result.Val)
    } else {
        fmt.Println("No intersection")
    }

    // test the two-pointer version
    result2 := getIntersectionNodeTwoPointer(headA, headB)
    if result2 != nil {
        fmt.Printf("Two-pointer result: %d\n", result2.Val)
    } else {
        fmt.Println("No intersection (two-pointer)")
    }
}

Running this program should output Intersection at node with value: 8 for both implementations, confirming that the shared node was correctly identified.

Testing the No-Intersection Case

It is equally important to verify that the algorithm returns nil when the lists do not intersect. The two-pointer approach handles this gracefully because both pointers will eventually become nil at the same time after switching lists once.

func testNoIntersection() {
    listA := buildList([]int{2, 6, 4})
    listB := buildList([]int{1, 5})

    result := getIntersectionNodeTwoPointer(listA, listB)
    if result == nil {
        fmt.Println("Correctly detected no intersection")
    } else {
        fmt.Printf("Unexpected intersection at %d\n", result.Val)
    }
}

Best Practices

• Compare by reference, not by value. The intersection is defined by node identity. Comparing Val fields will produce false positives when lists merely contain equal values.
• Handle edge cases explicitly. Always check for nil heads before traversal to avoid nil pointer dereferences.
• Prefer the two-pointer approach in interviews. It is concise, easy to explain, and demonstrates a deeper understanding of the problem's symmetry.
• Write clear test cases. Construct shared tails deliberately so that your tests genuinely exercise the intersection logic rather than coincidentally matching values.
• Avoid modifying the input lists. Both approaches above are non-destructive, which is important when the lists are shared or reused elsewhere in a program.
• Document the time and space complexity. Both solutions run in O(m + n) time and O(1) space, which is optimal. Being able to articulate this is valuable in interviews and code reviews.

Common Pitfalls

One frequent mistake is assuming that the intersection occurs at the first node with matching values. This is incorrect because the lists may have identical values at different positions without sharing memory. Always compare pointers, not values.

Another pitfall is forgetting to switch pointers back to the opposite head in the two-pointer approach. If you simply advance both pointers to nil and stop, you will miss the alignment that occurs on the second pass.

Finally, be cautious with cyclic lists. The problem assumes acyclic lists. If cycles are possible, additional cycle detection (such as Floyd's algorithm) is required before applying these techniques.

Conclusion

Solving the intersection of two linked lists in Go is a rewarding exercise that highlights the power of pointer manipulation and algorithmic symmetry. Whether you choose the explicit length-difference method or the elegant two-pointer technique, both deliver optimal O(m + n) time and O(1) space performance. By understanding the underlying mechanics — shared memory, length alignment, and reference comparison — you not only solve this specific problem but also build intuition that transfers to a wide range of linked list challenges. Practice both implementations, write thorough test cases, and you will be well prepared to handle this problem confidently in any technical interview or production codebase.