Данный вопрос попался моему другу на собеседовании. Сходу я предложил 2 варианта нахождения зацикленности, однако с предложенными вариантами выяснилось что список нельзя копировать и мутировать ;) Путем нехитрых манипуляций с поисковиком был обнаружен алгоритм Флойда для нахождения цикличности в списках.

Зацикленность в списке выглядит так:

Мои первые идеи

Теория

Для решения данной задачи все уже придумано. Алгоритм Флойда для нахождения зацикленности в списке

Алгоритм достаточно прост (странно что мне не пришло это в голову).

Итерируемся по списку с 2 разными скоростями, первый узел перемещаем на +1 (перебираем по порядку), второй узел +2, если хотя бы 1 из узлов null - считаем что список не зациклен, если узлы переменные имеют одинаковый указатель (т.е. переменная) идущая с шагом +1 столкнулась с переменой, идущей с шагом +2 то список является зацикленным.

Данный алгоритм иногда называют алгоритмом "Черепахи и зайца", из-за одноименной гречиской притчи

Псевдокод

// Функция определения зацикленности списка алгоритмом Флойда
    // Если текущая node nil либо следующая за ней nil
        // список не зациклен
        // завершаем сопрограмму
    // инициализируем переменную для +1 итерации (наша черепашка)
    // инициализируем переменную для +2 итераций (зайчик)
    // выполняем до того как медленная нода = быстрой, либо 1 из узлов указывает на nil
        // если указатель первой переменной равен указателю 2 переменной:
            // список является зацикленным
            // прерываем функцию
        // если следующее значение быстрой переменной равно nil или следующее>следующее значение nil:
            // Завершаем функцию, список не является зацикленным
        // Присваиваем в переменную для +1 итерации значение следующего узла
        // Присваиваем в переменную для +2 итерации значение следующего узла за следующим
    // Вышли из цикла, список не является зацикленным (такое поведение, впринципе, невозможно)

Реализация

Для начала реализуем структуру списка

package main

import (
    "fmt"
    "strconv"
)

type node struct {
    val  int
    next *node
}

type List struct {
    firstNode *node
    lastNode  *node
}

func NewList() *List {
    return &List{}
}

func (l *List) Add(val int) {
    if l.firstNode == nil {
        l.firstNode = &node{val: val}
        l.lastNode = l.firstNode
        return
    }
    l.lastNode.next = &node{val: val}
    l.lastNode = l.lastNode.next
}

func (l *List) String() string {
    currentNode := l.firstNode
    res := ""
    for currentNode != nil {
        res += strconv.Itoa(currentNode.val) + ", "
        currentNode = currentNode.next
    }
    res = "LIST: [" + res[:len(res)-2] + "]"
    return res
}

Теперь можем имплементировать наш псевдокод. Реализация алгоритма Флойда:

// Функция определения зацикленности списка алгоритмом Флойда
func IsListLooped(l *List) bool {
    // Если текущая node nil либо следующая за ней nil
    if l.firstNode == nil || l.firstNode.next == nil {
        // список не зациклен
        // завершаем сопрограмму
        return false
    }

    // инициализируем переменную для +1 итерации (наша черепашка)
    turtleNode := l.firstNode
    // инициализируем переменную для +2 итераций (зайчик)
    hareNode := l.firstNode.next

    // выполняем до того как медленная нода = быстрой, либо 1 из узлов указывает на nil
    for {
        // если указатель первой переменной равен указателю 2 переменной:
        if turtleNode == hareNode {
            // список является зацикленным
            return true
        }
        // если следующее значение быстрой переменной равно nil или следующее>следующее значение nil:
        if hareNode.next == nil || hareNode.next.next == nil {
            // Завершаем функцию, список не является зацикленным
            return false
        }
        // Присваиваем в переменную для +1 итерации значение следующего узла
        turtleNode = turtleNode.next
        // Присваиваем в переменную для +2 итерации значение следующего узла за следующим
        hareNode = hareNode.next.next
    }
    // Цикл пройден, список не зациклен
    return false
}

Реализацию, как и всегда, можно посмотреть на github