Middle of the linked list - Leetcode

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.

Example 1:
Input: [1,2,3,4,5] Output: Node 3 from this list (Serialization: [3,4,5]) The returned node has value 3. (The judge's serialization of this node is [3,4,5]). Note that we returned a ListNode object ans, such that: ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, and ans.next.next.next = NULL.

Example 2:
Input: [1,2,3,4,5,6] Output: Node 4 from this list (Serialization: [4,5,6]) Since the list has two middle nodes with values 3 and 4, we return the second one.

Here it can be done in two ways.

Option 1:

1)Take two pointers one as slow and other as fast.

2)Initially both pointing to the head.

3)Slow points the next element and fast points next of next element.

4)Step 3 has to repeated until fast equal to null and fast of next equal to null.

5)After this point, slow will points only at the 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) {
        if(head == null || head.next == null){
            return head;
        }
       
        ListNode slow = head;
        ListNode fast = head;
       
        while(fast!=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
       
        return slow;
    }
}

Option 2:

1)Find the length of the linked list by traversing through it.

2)By using that size and also traversing again you can easily find out the middle element of the linked list.

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode cur = head;
        int size = 0;
        while(cur != null) {
            cur = cur.next;
            size++;
        }
        cur = head;
        for (int i = 0; i < size / 2; i++) {
            cur = cur.next;
        }
        return cur;
    }
} 

Click this link to try it on Leetcode

For further queries or have a different solution leave as a comment..