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