Finding the Middle of a Linked List (with Animated Examples)by@akankov

# Finding the Middle of a Linked List (with Animated Examples)

December 18th, 2022

Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.

If there are two middle nodes, return the second middle node.

## Example 1:

Input: head = [1,2,3,4,5] Output: [3,4,5] Explanation: The middle node of the list is node 3.

## Example 2:

Input: head = [1,2,3,4,5,6] Output: [4,5,6] Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

## Constraints:

The number of nodes in the list is in the range [1, 100]. 1 <= Node.val <= 100

## Solution

### Approach 1: Two Passes

1. Find the length of the linked list by traversing the list.
2. Find the middle node by traversing the list again to the middle.
3. Return the middle node
``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
length = 0
while current:
length += 1
current = current.next

middle = length // 2
for _ in range(middle):
current = current.next

return current
``````

Time complexity: O(n) Space complexity: O(1)

### Approach 2: One Pass

1. Use two pointers, one fast and one slow.
2. Move the fast pointer two nodes at a time and the slow pointer one node at a time.
``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
while fast and fast.next:
slow = slow.next
fast = fast.next.next

return slow
``````

Time complexity: O(n) Space complexity: O(1)

L O A D I N G
. . . comments & more!