数据结构：环形链表-约瑟夫环

定义节点

type CircularNode struct {
    No   int
    Next *CircularNode
}

定义环形链表

type CircularLinkedList struct {
    first *CircularNode
}

初始化链表

func (list *CircularLinkedList) Init(nums int) {
    if nums < 1 {
        return
    }

    var temp *CircularNode
    for i := 1; i <= nums; i++ {
        node := &CircularNode{No: i}
        if i == 1 {
            list.first = node
            list.first.Next = list.first
            temp = list.first
        } else {
            temp.Next = node
            node.Next = list.first
            temp = temp.Next
        }
    }
}

出队列 方式一

因为是单链表，出队列需找到需要出队列的前一个节点。

首先找到开始节点的前一个节点。其次定义计数器，开始循环遍历，若计数器等于间隔数减1时将节点出队列，并重置计数器，反之计数器累加，指针后移。

func (list *CircularLinkedList) Pop(listLen, startNo, interval int) {
    if startNo < 1 || startNo > listLen {
        fmt.Println("参数不合法")
        return
    }
    temp := list.first

    // 找开始节点的前一个节点
    for {
        if temp.Next.No == startNo {
            break
        }
        temp = temp.Next
    }

    count := 0

    for {
        if count+1 == interval {
            fmt.Println("出圈 No#", temp.Next.No)
            if temp == temp.Next { // 只剩下一个节点
                break
            }
            count = 0
            temp.Next = temp.Next.Next
            continue
        }
        count++
        temp = temp.Next
    }
}

出队列 方式二

首先找到开始节点的前一个节点temp。然后再定义一个指针temp2指向开始节点，每次将temp和temp2指针移动指定间隔数减1次（因为单链表删除节点，需借助删除节点的前一个节点），最后将temp2赋值为temp2的下一个节点，

func (list *CircularLinkedList) Pop2(listLen, startNo, interval int) {
    if startNo < 1 || startNo > listLen {
        fmt.Println("参数不合法")
        return
    }
    temp := list.first

    // 找开始节点的前一个节点
    for {
        if temp.Next.No == startNo {
            break
        }
        temp = temp.Next
    }

    countPointer := temp.Next // 指向开始节点
    for  {
        if temp == countPointer {
            fmt.Println("出圈 No#", countPointer.No)
            break
        }
        for i := 0; i < interval-1; i++ {
            countPointer = countPointer.Next
            temp = temp.Next
        }

        fmt.Println("出圈 No#", countPointer.No)
        countPointer = countPointer.Next
        temp.Next = countPointer
    }
}

测试代码

func main() {

    circularLinkedList := &CircularLinkedList{}
    circularLinkedList.Init(5)
    circularLinkedList.Print()

    circularLinkedList.Pop(5, 1, 1)
    //circularLinkedList.Pop2(5, 1, 2)
}

func (list *CircularLinkedList) Print() {
    temp := list.first
    for temp != nil {
        fmt.Println("No#", temp.No)
        if temp.Next == list.first {
            return
        }
        temp = temp.Next
    }
}