easyLinked ListPattern: Slow & Fast Pointer
Middle Node of a Singly Linked List Solution
Problem Statement
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. The linked list is guaranteed to have at least one node.
Examples
Example 1:
Input:1->2->3->4->5
Output:3
Explanation: The linked list has 5 nodes. The middle node is the 3rd node, which is 3.
Example 2:
Input:1->2->3->4->5->6
Output:4
Explanation: The linked list has 6 nodes. There are two middle nodes, 3 and 4. Since we return the second middle node, the answer is 4.
Example 3:
Input:1
Output:1
Explanation: The linked list has only one node. The middle node is the 1st node, which is 1.
Constraints
- The number of nodes in the list is in the range [1, 100].
- Node values are integers.
- The list is singly linked.
Time: O(N) Space: O(1)
Use the 'slow and fast pointer' technique. Initialize two pointers, `slow` and `fast`, to the head of the list. Move `slow` one step at a time and `fast` two steps at a time. When `fast` reaches the end of the list (or `fast.next` is null), `slow` will be pointing to the middle node.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow