find the median of all nodes in a linked list in swift

To find the median of all nodes in a linked list, we can follow below steps:

1. Find the length of the linked list
2. If the length is odd, traverse to the middle element and return its value
3. If the length is even, traverse to the middle two elements and return their average

Here's the Swift code to implement the above steps:

main.swift
class Node {
    var value: Int
    var next: Node?

    init(_ value: Int, _ next: Node? = nil) {
        self.value = value
        self.next = next
    }
}

func findMedian(_ head: Node?) -> Double {
    var slow = head
    var fast = head
    var count = 0

    while fast != nil && fast?.next != nil {
        slow = slow?.next
        fast = fast?.next?.next
        count += 1
    }

    if count % 2 == 0 {
        return Double((slow?.value ?? 0) + (slow?.next?.value ?? 0)) / 2.0
    } else {
        return Double(slow?.value ?? 0)
    }
}
551 chars
28 lines

Here, we traverse the linked list using two pointers - a slow pointer and a fast pointer. The fast pointer moves twice as fast as the slow pointer. When the fast pointer reaches the end of the linked list, the slow pointer would have reached the middle of the list. We keep count of the number of nodes traversed to determine if the list has an odd or even length.

Finally, we return the median as a Double value.