Solution For Middle Of The Linked List

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.

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:

def middleNode(head: ListNode) -> ListNode:
slow = head
fast = head

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

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        // create two pointers, one that moves at twice the speed of the other
        ListNode slow = head;
        ListNode fast = head;
        
        // 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
        slow = head
        fast = head
        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: 

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var middleNode = function(head) {
    //create a slow and fast pointer
    let slow = head;
    let fast = head;
    
    //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;
};

/**
 * 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) {
        //Edge case: If head is null or there is only one node in the list
        if(head==NULL || head->next==NULL)
            return head;
        
        //Slow and fast pointers to reach the middle of the list
        ListNode* slow=head;
        ListNode* fast=head;
        
        //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;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode MiddleNode(ListNode head) {
        
        //create a slow and fast pointer
        ListNode slow = head;
        ListNode fast = head;
        
        //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;
    }
}