Skip to content

Instantly share code, notes, and snippets.

@hkurokawa
Last active February 20, 2019 14:48
Show Gist options
  • Save hkurokawa/21bfe40665665fb51dbd27e6587fea4d to your computer and use it in GitHub Desktop.
Save hkurokawa/21bfe40665665fb51dbd27e6587fea4d to your computer and use it in GitHub Desktop.
Detect loop of the given LinkedList
class LinkedListNode(var next: LinkedListNode?, val value: String)
fun detectLoop(list: LinkedListNode): String {
var node1 = list
var node2 = list
var n = 0
do {
node1 = node1.next!!
node2 = node2.next!!.next!!
n++
} while (node1 != node2)
node1 = list
node2 = list
while (n > 0) {
node2 = node2.next!!
n--
}
while (node1 != node2) {
node1 = node1.next!!
node2 = node2.next!!
}
return node1.value
}
fun main() {
println(detectLoop(build(2, 3))) // A -> B -> C -> D -> E -> C
println(detectLoop(build(3, 2))) // A -> B -> C -> D -> E -> D
println(detectLoop(build(1, 1))) // A -> B -> B
println(detectLoop(build(1, 5))) // A -> B -> C -> D -> E -> F -> B
println(detectLoop(build(4, 2))) // A -> B -> C -> D -> E -> F -> E
println(detectLoop(build(5, 1))) // A -> B -> C -> D -> E -> F -> F
}
fun build(i: Int, L: Int): LinkedListNode {
val last = LinkedListNode(null, ('A' + i + L).toString())
var list = last
repeat(i + L - 1) { idx ->
list = LinkedListNode(list, ('A' + i + L - idx - 1).toString())
}
var node = list
repeat(i - 1) {
node = node.next!!
}
last.next = node
return list
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment