2021-08-12：约瑟夫环问题。给定一个链表头节点head，和一个正数m，从头开始，每次数到m就杀死当前节点 ，然后被杀节点的下一个节点从1开始重新数， 周而复始直到只剩一个节点，返回最后的节点。
福大大 答案2021-08-12：
递推式f(n)=(f(n-1) m-1)%n 1。
时间复杂度：O(n)。
空间复杂度：改成迭代，可优化成O(1)。
代码用golang编写。代码如下：
代码语言：txt复制package main
import "fmt"
func main() {
head := NewNode(1)
head.next = NewNode(2)
head.next.next = NewNode(3)
head.next.next.next = NewNode(4)
head.next.next.next.next = NewNode(5)
head.next.next.next.next.next = head
ret := josephusKill2(head, 3)
fmt.Println(ret.value)
}
type Node struct {
value int
next *Node
}
func NewNode(data int) *Node {
ans := &Node{}
ans.value = data
return ans
}
func josephusKill2(head *Node, m int) *Node {
if head == nil || head.next == head || m < 1 {
return head
}
cur := head.next
size := 1 // tmp -> list size
for cur != head {
size
cur = cur.next
}
live := getLive(size, m) // tmp -> service node position
live--
for live != 0 {
head = head.next
live--
}
head.next = head
return head
}
func getLive(n int, m int) int {
if n == 1 {
return 1
}
return (getLive(n-1, m) m-1)%n 1
}执行结果如下：
图片左神java代码
