Leetcode (Linked list pattern)

141. Linked List Cycle

2 ways to approach this problem

• Keep track of all nodes you have visited in a HashSet. If you notice that you have already visited a given node, return true. This solution takes O (n) space and O (n) time. If the iterator reaches null, there is no cycle.

• Take a fast pointer and a slow pointer. Fast pointer moves twice as fast as the slow pointer. If the fast pointer reaches end, there is no cycle. If at any given point the fast pointer and slow pointer are the same node element, return truel. This solution takes O (1) space and O (n) time.

876. Middle of the Linked List

• Use two pointers, both initially pointing to head

• One moves twice as fast as the other

• When the fast one reaches the end of the linked list, the slower one will reach the middle

• Time : O (n), Space: O (1)

1

2

2

14