Leetcode Note: Go - Intersection of Two Linked Lists

Intersection of Two Linked Lists - LeetCode
https://leetcode.com/problems/intersection-of-two-linked-lists/

  • Go 言語で取り組んだメモ

所感

  • 2つ の Linked List が与えられた時に交差するノードを返す

回答

Golang solution with map - LeetCode Discuss
https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/908635/Golang-solution-with-map

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    hasVisited := make(map[*ListNode]bool)
    
    for n := headA; n != nil; n = n.Next{
        hasVisited[n] = true
    }
    
    for n := headB; n != nil; n = n.Next{
        if _, ok := hasVisited[n]; ok {
            return n
        }
    }
    return nil
}
  • headA または headB が nil かチェック
  • ListNode と bool のマップを定義
  • for loop
    • headA が nil になるまで n = n.Next を繰り返す
    • hasVisited[n] = true で headA の要素をマップに記録
  • for loop
    • headB が nil になるまで n = n.Next を繰り返す
    • hasVisted[n] が存在したら、その要素を return する
  • ループでノードが返せなかったら return nil

実装見たらシンプルだけど要件を読み解くのが難しかった・・・