约瑟夫问题

0.约瑟夫问题.png

找到首节点、创建一个节点记录遍历当前节点的前一个节点、创建一个计数器，当计数器的值为3的时候，将该节点从链表中移除，直到剩下最后一个节点。

 /// 约瑟夫问题
    private func testJoseph() {
        
        var firstNode = TNode<Int>(item: nil, next: nil)
        var pre = TNode<Int>(item: nil, next: nil)
        
        // 创建循环链表
        for i in 1...41 {
            if i == 1 {
                firstNode = TNode(item: i, next: nil)
                pre = firstNode
                continue
            }
            
            let node = TNode(item: i, next: nil)
            pre.next = node
            pre = node
            
            if i == 41 {
                pre.next = firstNode
            }
        }
        
//        var testNode = firstNode
//        while testNode.next?.item != 1 {
//            testNode = testNode.next!
//            print("\(testNode.item ?? 0)")
//        }
        
        var n = firstNode
        var before = TNode<Int>(item: nil, next: nil)
        var count = 0
        /// 将计数为3的节点移除
        while n.next != n {
            count += 1
            if count == 3 {
                before.next = n.next
                print("\(n.item ?? 0)")
                count = 0
                n = n.next!
            } else {
                before = n
                n = n.next!
            }
        }
        
        print("最后剩下：\(n.item ?? 0)")
    }

demo地址：https://github.com/yangguanghei/studyDateStructure