Find the Intersection Point of Two Linked Lists in Go

Program Code

package main

import "fmt"

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

// getIntersectionNode finds the intersection point of two linked lists
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }

    a, b := headA, headB

    // Traverse both lists
    for a != b {
        // Move to the next node, or switch to the other list when reaching the end
        if a == nil {
            a = headB
        } else {
            a = a.Next
        }

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

    return a
}

// Helper function to print the linked list
func printList(head *ListNode) {
    for head != nil {
        fmt.Print(head.Val, " ")
        head = head.Next
    }
    fmt.Println()
}

// Main function to test the getIntersectionNode function
func main() {
    // Create two intersecting linked lists
    // List A: 1 -> 2 -> 3
    //                        \
    //                         7 -> 8
    //                        /
    // List B:       4 -> 5

    // Create shared part of the linked list
    intersect := &ListNode{7, &ListNode{8, nil}}

    // Create List A
    headA := &ListNode{1, &ListNode{2, &ListNode{3, intersect}}}

    // Create List B
    headB := &ListNode{4, &ListNode{5, intersect}}

    fmt.Print("List A: ")
    printList(headA)

    fmt.Print("List B: ")
    printList(headB)

    // Find the intersection node
    intersection := getIntersectionNode(headA, headB)

    if intersection != nil {
        fmt.Printf("The intersection point is: %d\n", intersection.Val)
    } else {
        fmt.Println("The lists do not intersect.")
    }
}
    

Explanation

The Go program is designed to find the intersection point of two singly linked lists. Here is a detailed explanation of the program structure:

1. ListNode Definition

The ListNode struct defines a node in a singly linked list, which contains a value (Val) and a pointer to the next node (Next).

2. getIntersectionNode Function

The getIntersectionNode function finds the intersection point of two linked lists:

• Initializes two pointers, a and b, which start at the heads of the two linked lists.
• Traverses both lists simultaneously:
  • Moves a and b to the next node, or switches to the head of the other list when reaching the end.
  • This ensures that both pointers traverse the same total length and meet at the intersection point if one exists.
• Returns a (or b, as they will be equal when they meet), which will be either the intersection node or nil if there is no intersection.

3. printList Function

The printList function is a utility to print out the values of the linked list for demonstration purposes.

4. Main Function

The main function demonstrates the usage of the getIntersectionNode function:

• Creates two linked lists that intersect at node 7.
• Prints both lists.
• Finds the intersection point using getIntersectionNode and prints the value of the intersection node.
• If there is no intersection, it prints a message indicating that the lists do not intersect.