kotlin-coding-challenges

Linked list midpoint

Nice to solve before

Linked List.kt

Instructions

Return the ‘middle’ node of a linked list. If the list has an even number of elements, return the node at the end of the first half of the list.

We are using version of linked list that implements Kotlin Iterator interface, so we can use forEach instead of while loop.

Challenge

Solution

Limitations

Do not use a counter variable, do not retrieve the size of the list, and only iterate through the list one time.

Examples

Example 1

val l = new LinkedList()
l.insertLast('a')
l.insertLast('b')
l.insertLast('c')
midpoint(l).data // 'b'

Example 2

val l = new LinkedList()
l.insertLast('a')
l.insertLast('b')
l.insertLast('c')
l.insertLast('d')
midpoint(l).data // 'b'

Hints

Hint 1

Use more then one variable to store values that are retrieved during iteration (double pointer solution)

Hint 2

Name of these variables should be `slow` and `fast`

Hint 3

Assign next node to `slow` variable in every iteration

Hint 4

Assign next node of next node to `fast` variable in every iteration

This site is open source. Improve this page.