leecode探索チェーンテーブルリングチェーンテーブルII

タイトル
チェーンテーブルが与えられ、チェーンテーブルがループを開始した最初のノードを返します.チェーンテーブルにループがない場合はnullを返します.
与えられたチェーンテーブルのループを表すために、整数posを使用してチェーンテーブルの最後にチェーンテーブルに接続された位置を表します(インデックスは0から始まります).posが-1の場合、チェーンテーブルにリングはありません.説明:指定したチェーンテーブルの変更は許可されていません.例1:
入力:head=[3,2,0,-4],pos=1出力:tail connects to node index 1解釈:チェーンテーブルにループがあり、その末尾が2番目のノードに接続されています.ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/linked-list-cycle-ii
ぶんせき
三種類の解法

ListNodeにcountベースを追加して+1にアクセスし、遭遇カウントが2の場合は2回アクセスされたことを示し、ループの開始である.

両指針法、速遅針、速針は2歩、遅針は1歩、環があれば出会う.ループが見つかった後、新しいポインタは最初から、遅いポインタは前に進み続け、図を描くと明らかに見えるはずで、二人はまた同じ点で出会う.

は補助空間O(N)を借りて、1つのhashmapを採用して、訪問したのはhashmapの中に参加して、hashmapの中ですでにあったことに出会って、環に出会ったことを表明して、

解法

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



func detectCycle(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return nil
    }

    slow, fast := head, head.Next
    for slow != fast {
        if fast == nil || fast.Next == nil {
            return nil
        }
        slow = slow.Next
        fast = fast.Next.Next
    }

    // fmt.Printf("  
")
    //       ，    
    // aNew   0   ， slow    -1  
    slow = slow.Next
    for aNew := head; aNew != slow; aNew, slow = aNew.Next, slow.Next {
        // fmt.Printf("1: %v, 2: %v
", aNew.Val, slow.Val)
    }

    return slow
}

解法2

unc detectCycle(head *ListNode) *ListNode {
    var mm = make(map[*ListNode]bool)
    cur := head
    for cur != nil {
        if _, ok := mm[cur]; ok {
            return cur
        }
        mm[cur] = true
        cur = cur.Next
    }
    return nil
}