funclear() { var n = first while (n != null) { val next = n.next // 快速gc n.item = null n.next = null n.prev = null n = next } first = null last = null _size = 0 }
privatefungetNode(index: Int): Node<T> { val reIndex = index % _size returnif (reIndex < (_size shr 1)) { var node = first for (i in0 until index) { node = node?.next } node!! } else { var node = last for (i in _size - 2 downTo index) { node = node?.prev } node!! } }
/** * 连接尾节点 * */ privatefunlinkedLast(item: T) { val l = last val nNode = Node(item, l, null) last = nNode
if (l == null) { first = last } else { l.next = nNode } first!!.prev = nNode nNode.next = first _size++ }
/** * 解连接 * */ privatefununlink(node: Node<T>): T { val npre = node.prev val nnext = node.next val nitem = node.item
if (npre == last && nnext == first) { last = null first = null } else { if (node == first) first = nnext if (node == last) last = npre npre!!.next = nnext nnext!!.prev = npre node.next = null node.prev = null }
node.item = null _size-- return nitem!! }
/** * 转字符串方法 * */ overridefuntoString(): String { when (_size) { 0 -> return"[]" else -> { val sb = StringBuilder() sb.append("[") var n = first while (n != last) { sb.append("${n!!.item}, ") n = n.next } return sb.append("${n!!.item}]").toString() } } }
companionobject { privatedataclassNode<T>( var item: T?, var prev: Node<T>?, var next: Node<T>? )
funlinkedListForceSolution(): String { val sb = StringBuilder() val cl = CircularLinkedList<Int>().apply { for (i in1..totalPeople) add(i) } val iter = cl.iterator()
var cnt = 0 while (iter.hasNext() && cl.size != remainPeople) { iter.next() cnt++ if (cnt == intervalPeople) { iter.remove() cnt = 0 } }
/** * 双向队列暴力求法 * 就是嗯求 * */ funqueueForceSolution(): String { val sb = StringBuilder() // 初始化队列 val deque = Deque<Int>().apply { for (i in1..totalPeople) pushRight(i) }
// 没有到剩余人数就继续循环 while (deque.size != remainPeople) { // 跳过间隔人数 // 这里的跳过为了不影响后面的循环做的是左出右进的方案 for (q in1 until intervalPeople) deque.pushRight(deque.popLeft()) deque.popLeft() }
return sb.apply { deque.forEachIndexed { index, i -> append("${i}号") if (index != deque.size - 1) append(", ") } }.toString() }
funlinkedListForceSolution(): String { val sb = StringBuilder() val cl = CircularLinkedList<Int>().apply { for (i in1..totalPeople) add(i) } val iter = cl.iterator()
var cnt = 0 while (iter.hasNext() && cl.size != remainPeople) { iter.next() cnt++ if (cnt == intervalPeople) { iter.remove() cnt = 0 } }