这是经典的约瑟夫环，并且期望剩余的人数是2，我们这里也做了一个通配，可以输入期望剩余的人数，比如期望剩余1个，那么31这个位子可以存活。当然解决关键就是得用到单向循环链表，语言自然选择的是golang，当然这算是第一版本以实现功能为主，还有很多待改进的地方。

Let’s go

第一.我们先演绎一下，我们从1开始报数，到三的时候自杀，然后以此类推6、9、12…可以看得出来第一圈是以3的倍数自杀，最后到39跑完一圈。

第二.我们再跑一圈，第一圈的最后一个是39，那么+3以后这次应该是1自杀，以此类推+3的偏移量，如果中间遇到已经死亡的，我们不计数。

这样第二圈跑完下来最后一个自杀的应该是41。我们就按照以上思路进行编写，其实程序也就是我们的思考过程，只不过我们只是做了前期归纳演算，最后的规律以及实现方式还得用计算机来实现这就是计算机存在的意义。

第三.我们可以从上面的图里看出，这是一个环状的结构，那么我们要实现这样的结构，就可以用一种数据结构来表示——单向循环 链表 。我们用一张图来解释这个链表：

从图中可以看到，链表的尾部元素的Next是永远指向Head的，这样就形成了一个环。

好了，废话不多说了，上代码。

1.定义结构体，这里Index表示表示元素的下标，Killed表示是否已经被杀，false表示存活。

 type Node struct {
Index  int
Killed bool
Next   *Node
}

type LinkedList struct {
Head *Node
Len  int
*Node
}  

2.插入元素，这里只讨论尾部插入，其余的不做研究。当Head为nil的时候，插入第一个元素就是Head，同时Head的Next指向的是Head。其余新增的元素的Next一定得指向Head，形成闭环。

 func (list *LinkedList) insert(index int) {
node := &Node{Index: index}
list.Len++

if list.Head == nil {
list.Head = node
list.Head.Next = node
list.Node = node
return
}

curr := list.Head
for curr.Next != list.Head {
curr = curr.Next
}

curr.Next = node
node.Next = list.Head
}  

3.实现报数自杀。这里可输入期望存活的人数，返回的是一个数组，数组里存的是下标。

 func (list *LinkedList) selfKilled(aliveNums int) []int {
curr := list.Head
offset := 1
killNum := list.Len
for killNum > aliveNums {
if offset%3 == 0 {
curr.Killed = true
offset = 0
killNum--
}
offset++
curr = curr.Next
for curr.Killed {
curr = curr.Next
}
}

aliveArr := make([]int, 0)
h := list.Head
for h.Next != list.Head {
h = h.Next
if !h.Killed {
aliveArr = append(aliveArr, h.Index)
}
}

return aliveArr
}  

4.遍历插入元素，实现41个人排队手拉手。

 func josephusProblem(aliveNums int) []int {
list := &LinkedList{}
for i := 1; i < 42; i++ {
list.insert(i)
}
return list.selfKilled(aliveNums)
}  

5.最后必不可少的main函数入口。

 func main() {
expectedAliveNums := 2
fmt.Printf("real alive indexs:%v\n", josephusProblem(expectedAliveNums))
}  

6.我们期望的值是16和31，这里不做test表格驱动测试了，就用简单的main输出。

 real alive indexs:[16 31]  

7.收工，整体下来主要逻辑在于selfKilled方法，这里循环遍历有点啰嗦，还有待改进，留着以后再做调整吧。