输入两个链表，找出它们的第一个公共节点

golang版

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

// 辣鸡程序员算法
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    // 压入两个栈，然后同时pop
    stack1, stack2 := []*ListNode{}, []*ListNode{}

    // 加入两个虚拟头节点，方便计算头节点就是共同节点的情况
    stack1 = append(stack1, &ListNode{0, headA}) 
    stack2 = append(stack2, &ListNode{0, headB}) 

    for headA != nil {
        stack1 = append(stack1, headA)
        headA = headA.Next
    }

    for headB != nil {
        stack2 = append(stack2, headB)
        headB = headB.Next
    }

    var ele1, ele2 *ListNode
    var flag = false
    for len(stack1) != 0 && len(stack2) != 0 {
        ele1, ele2 = stack1[len(stack1)-1], stack2[len(stack2)-1]
        if ele1 != ele2 {
            flag = true
            break
        }
        stack1 = stack1[:len(stack1)-1]
        stack2 = stack2[:len(stack2)-1]
    }
    if flag {
        return ele1.Next
    }
    
    return nil
}

// 《你的名字》算法
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    /* 你变成我，走过我走过的路。
    我变成你，走过你走过的路。
    然后我们便相遇了..
    */
    
    begin_a, begin_b := headA, headB
    // 只要未曾相遇
    for headA != headB {
        
        if headA != nil {
            headA = headA.Next
        }else{
            // 你变成我，走过我走过的路。
            headA = begin_b
        }

        if headB != nil {
            headB = headB.Next
        }else{
            // 我变成你，走过你走过的路。
            headB = begin_a
        }
    }
    // 然后我们便相遇了..
    return headA

}

有疑问加站长微信联系（非本文作者）