iOS Interview - Leetcode 876. Middle of the Linked List

June 12, 2024 • 2 min read • #swift, #interview, #leetcode

Leetcode: 876. Middle of the Linked List

Primary idea: Slow and fast pointers, where fast pointer moves 2 steps and slow point moves 1 step at a time
Time Complexity: O(n), where n is the number of nodes in the linked list.
Space Complexity: O(1), only constant space is used.

public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init(_ val: Int) {
        self.val = val
        self.next = nil
    }

    public func print() {
        var node: ListNode? = self
        var result = ""
        while node != nil {
            result += "\(node!.val)"
            node = node?.next
            if node != nil {
                result += " -> "
            }
        }
        Swift.print(result)
    }
}

func middleNode(_ head: ListNode?) -> ListNode? {
    var slow = head
    var fast = head

    while let fastNext = fast?.next {
        slow = slow?.next
        fast = fastNext.next
    }

    return slow
}

let head1 = ListNode(1)
head1.next = ListNode(2)
head1.next?.next = ListNode(3)
head1.next?.next?.next = ListNode(4)
head1.next?.next?.next?.next = ListNode(5)
head1.print()
print(middleNode(head1)?.val ?? "nil") // 3

let head2 = ListNode(1)
head2.next = ListNode(2)
head2.next?.next = ListNode(3)
head2.next?.next?.next = ListNode(4)
head2.next?.next?.next?.next = ListNode(5)
head2.next?.next?.next?.next?.next = ListNode(6)
head2.print()
print(middleNode(head2)?.val ?? "nil") // 4