Finding middle element in a linked list

Link:-

Middle of the Linked List - LeetCode

Finding middle element in a linked list | Practice | GeeksforGeeks

Description :-

Given a singly linked list of N nodes. The task is to find the middle of the linked list.

For example, if given linked list is 10->20->30->40->50 then the output should be 30.

If there are even nodes, then there would be two middle nodes, we need to print the second middle element. For example, if given linked list is 1->2->3->4->5->6 then the output should be 4.

Example 1:

Input:
LinkedList: 1->2->3->4->5
Output: 3

Example 2:

Input:
LinkedList: 2->4->6->7->5->1
Output: 7

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 <= N <= 5000

Method 1 :-

Step 1:Traverse the linked list from head till the end node. Count the number of nodes while traversing the linked list.

Step 2 : Count of number of nodes in linked list divided by 2 will give the middle value.

Step 3 :Again traverse the linked list from head node till mid value. Finally, return the data in the middle node.

Below is the java solution for this problem:

class Solution {
    public ListNode middleNode(ListNode head) {
        
       // get the length of the linked list
    int len = 0;
    ListNode current = head;
    while (current != null) {
        len++;
        current = current.next;
    }
    current = head;
    int mid = len / 2;
    for (int i = 0; i < mid; i++) {
        current = current.next;
    }
    return current;
    }
}

Method 2 :-

Step1: Create two pointers fast and slow. Both this pointers will point to the start of the head in the beginning.

Step 2 :Then, increment the fast pointer by 2 nodes and the slow pointer by one node.

Step 3: When the fast pointer will reach the end of the list then slow pointer will reach till the middle of the list and we will get our result.

Below is the java solution for this problem:

class Solution {
    public ListNode middleNode(ListNode head) {
        
        if(head == null){
            return head;
        }
        
        ListNode slow = head;
        ListNode fast = head;
        
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
        
    }
}