Golang判断两个链表是否相交的方法详解

在判断两个链表是否相交的时候，可以使用双指针的方法实现。

双指针方法

首先需要定义两个指针，分别指向两个链表的头结点，然后同时遍历两个链表，直到到达它们的尾部。如果两个链表相交，那么它们在相交点之后的结点都是相同的，因此在遍历结束前，两个指针必定会指向同一个结点。

请参考下面的代码示例：

type ListNode struct {
        Val int
        Next *ListNode
}

func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    p, q := headA, headB
    for p != q {
        if p == nil {
            p = headB
        } else {
            p = p.Next
        }
        if q == nil {
            q = headA
        } else {
            q = q.Next
        }
    }
    return p
}

代码中有两个指针p和q，它们分别指向链表headA和headB的头结点。在循环中，每次将p和q各自向后移动一步，直到它们相等或者同时到达链表的尾结点。

特别的，当其中一个指针到达链表的尾结点时，它需要将该指针的下一跳指向另一个链表的头结点，继续遍历。这是因为两个链表的长度可能不同，如果不进行这个操作，两个指针可能无法相遇。

示例说明

示例1

如下图所示，两个链表相交于结点c2。

链表A： a1 -> a2 -> c1 -> c2 -> c3

链表B： b1 -> b2 -> b3 -> c1 -> c2 -> c3

其中，圆点表示链表结点，箭头表示链表指针。

headA := &ListNode{Val: 1}
headA.Next = &ListNode{Val: 2}
headA.Next.Next = &ListNode{Val: 3}
headA.Next.Next.Next = &ListNode{Val: 4}
headA.Next.Next.Next.Next = &ListNode{Val: 5}

headB := &ListNode{Val: 2}
headB.Next = &ListNode{Val: 3}
headB.Next.Next = &ListNode{Val: 4}
headB.Next.Next.Next = &ListNode{Val: 5}

commonNode := &ListNode{Val: 6}
headA.Next.Next.Next.Next.Next = commonNode
headB.Next.Next.Next.Next = commonNode

result := getIntersectionNode(headA, headB)
fmt.Println(result.Val) // output: 6

在上面的示例中，我们创建了两个链表headA和headB，并且它们在结点c2处相交。我们将它们交错连接，并调用getIntersectionNode函数。

最后，该函数返回相交点的指针，即结点commonNode。

示例2

如下图所示，两个链表不相交。

链表A： a1 -> a2 -> a3 -> a4 -> a5

链表B： b1 -> b2 -> b3 -> b4 -> b5

headA := &ListNode{Val: 1}
headA.Next = &ListNode{Val: 2}
headA.Next.Next = &ListNode{Val: 3}
headA.Next.Next.Next = &ListNode{Val: 4}
headA.Next.Next.Next.Next = &ListNode{Val: 5}

headB := &ListNode{Val: 2}
headB.Next = &ListNode{Val: 3}
headB.Next.Next = &ListNode{Val: 4}
headB.Next.Next.Next = &ListNode{Val: 5}

result := getIntersectionNode(headA, headB)
fmt.Println(result) // output: nil

在上面的示例中，我们同样创建了两个链表headA和headB，并且它们不相交。我们调用getIntersectionNode函数，它将返回nil。

在实际编程过程中，我们可能需要考虑链表为空的情况，代码中已经添加了此判断。