로고조성현

0876 Middle of the Linked List

Solved at: 2023-01-29

Question

0876 Middle of the Linked List

Solution

class Solution {
    func middleNode(_ head: ListNode?) -> ListNode? {
        print("start")
        var count = 0
        var headcopy = head

        while(headcopy != nil) {
            headcopy = headcopy!.next
            count += 1
        }

        var fin = count / 2

        headcopy = head

        for _ in 0..<fin {
            headcopy = headcopy!.next
        }

        return (headcopy)
    }
}

Results

  • Runtime 3 ms Beats 84.39%
  • Memory 14.4 MB, Beats 13.82%

Complexity Analysis

  • O(N)O(N)
  • O(1)O(1)

Improved

class Solution {
    func middleNode(_ head: ListNode?) -> ListNode? {
        var fast = head
        var slow = head
        while (fast != nil && fast!.next != nil) {
            fast = fast!.next!.next
            slow = slow!.next
        }
        return slow
    }
}
  • Runtime 6 ms Beats 54.85%
  • Memory 14 MB, Beats 70.57%