Problem Statement:
Find the middle node of a singly linked list using the slow and fast pointer approach.
Approach:
- Use two pointers:
slowandfast. - Initialize both at the head of the list.
- Move
slowone step andfasttwo steps at a time. - When
fastreaches the end,slowwill be at the middle.
Examples:
- Input:
[1,2,3,4,5] - Output:
[3,4,5] - Explanation: The middle node is node
3.
- Input:
[1,2,3,4,5,6] - Output:
[4,5,6] - Explanation: There are two middle nodes:
3and4. We return the second one.
Constraints:
- The number of nodes in the list is in the range
[1, 100]. 1 <= Node.val <= 100
Time & Space Complexity:
- Time Complexity:
O(n) - Space Complexity:
O(1)
Use Case:
This technique is efficient with O(n) time and O(1) space, commonly used in problems like finding the start of a loop, checking palindromes, etc.
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var middleNode = function (head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
};# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def middleNode(self, head):
"""
:type head: Optional[ListNode]
:rtype: Optional[ListNode]
"""
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* middleNode(struct ListNode* head) {
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode MiddleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
