easyLinked ListPattern: Two Pointers
Middle Node of 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.
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.
Example 2:
Input:1->2->3->4->5->6
Output:3
Explanation: The linked list has 6 nodes. The middle nodes are the 3rd and 4th nodes. The problem states to return the identifier of the first node in the middle pair, which is the 3rd node.
Example 3:
Input:7
Output:7
Explanation: The linked list has 1 node. The middle node is the 1st node.
Constraints
- The number of nodes in the list is in the range [1, 100].
- Node values are integers.
- The list is guaranteed to be a valid singly linked list.
Time: O(N) Space: O(1)
Use the two-pointer technique. Initialize two pointers, `slow` and `fast`, both starting at the head. Move `slow` one step at a time and `fast` two steps at a time. When `fast` reaches the end of the list (or its next node 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
def middle_node(head: ListNode) -> ListNode:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow