# Solution For Middle Of The Linked List

Problem Statement:

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

Example:
Input: head = [1,2,3,4,5] Output: [3,4,5]

Solution:

To solve the problem, we can use two pointers, a slow pointer and a fast pointer. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. When the fast pointer reaches the end of the linked list, the slow pointer would have moved to the middle node.

Algorithm:

1. Initialize the slow pointer and fast pointer to the head of the linked list.
2. Traverse the linked list using the fast pointer until it reaches the end of the list.
3. During each iteration, move the slow pointer one step and the fast pointer two steps.
4. When the fast pointer reaches the end of the linked list, the slow pointer will be pointing at the middle node.
5. If there are even number of nodes, the slow pointer should point to the second middle node.
6. Return the middle node pointed by the slow pointer.

Pseudo Code:

``````while fast and fast.next:
slow = slow.next
fast = fast.next.next

return slow
``````

Code Explanation:

The above code defines the function middleNode which accepts the head of a singly linked list as input and returns the middle node of the linked list.

We initialize two pointers, slow and fast, to the head of the linked list. We then traverse the linked list using the fast pointer until it reaches the end of the list. During each iteration, we move the slow pointer one step and the fast pointer two steps. When the fast pointer reaches the end of the linked list, the slow pointer will be pointing at the middle node. If there are even number of nodes, the slow pointer should point to the second middle node. We then return the middle node pointed by the slow pointer.

Time Complexity:

The time complexity of the above algorithm is O(n/2) which can be simplified to O(n), where n is the number of nodes in the linked list. This is because, in the worst case scenario, we will have to traverse half of the linked list to get to the middle node.

Space Complexity:

The space complexity of the above algorithm is O(1) because we are not using any extra space.

## Step by Step Implementation For Middle Of The Linked List

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
// create two pointers, one that moves at twice the speed of the other

// while the fast pointer hasn't reached the end of the list
while (fast != null && fast.next != null) {
// move the slow pointer up one node
slow = slow.next;
// move the fast pointer up two nodes
fast = fast.next.next;
}

// return the node that the slow pointer is pointing to
// this will be the middle node of the list
return slow;
}
}```
```# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
def middleNode(self, head: ListNode) -> ListNode:
# set up two pointers, one moves one node at a time
# and the other moves two nodes at a time
# when the "fast" pointer reaches the end of the list,
# the "slow" pointer will be at the middle of the list
while fast != None and fast.next != None:
slow = slow.next
fast = fast.next.next
return slow```
```Given a non-empty, singly linked list with head node head, return a middle node of linked list.

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

//Solution:

/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @return {ListNode}
*/
//create a slow and fast pointer

//while loop to iterate through the list
while(fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
//return the slow pointer which will be in the middle of the list
return slow;
};```
```/**
* 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:
//Edge case: If head is null or there is only one node in the list

//Slow and fast pointers to reach the middle of the list

//Increment fast pointer by two nodes and slow pointer by one node in each iteration
//When fast pointer reaches the end of the list, slow pointer will be pointing to the middle of the list
while(fast!=NULL && fast->next!=NULL)
{
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
};```
```/**
* public class ListNode {
*     public int val;
*     public ListNode next;
*     public ListNode(int x) { val = x; }
* }
*/
public class Solution {

//create a slow and fast pointer

//move the fast pointer by 2 nodes and slow pointer by 1 node at a time
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}

//when the fast pointer reaches the end, the slow pointer will be pointing to the middle node
return slow;
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]