Find Middle of Linked List - DSA Practice

Given the head of a singly Linked List, return the middle node of the Linked List.

If the Linked List has an even number of nodes, return the second middle one.

Example 1:

Input: head -> 3 -> 8 -> 7 -> 1 -> 3

Output(value at returned node): 7

Explanation: There are 5 nodes, so the middle node is the 3^rd Node, with value 7.

Example 2:

Input: head -> 2 -> 9 -> 1 -> 4 -> 0 -> 4

Output(value at returned node): 4

Explanation: There are 6 nodes, thus both the 3^rd and 4^th nodes are middle. So the 2^nd middle node (4^th Node) is returned with value 4.

Now Your Turn!

Pick the correct output for the given input

Input: head -> 3 -> 8 -> 1 -> 7 -> 0

7812

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

1 <= number of Nodes in the Linked List <= 10⁵

-10⁴ <= ListNode.val <= 10⁴

Tab-1

1/*
2Definition of singly linked list:
3struct ListNode
4{
5    int val;
6    ListNode *next;
7    ListNode()
8    {
9        val = 0;
10        next = NULL;
11    }
12    ListNode(int data1)
13    {
14        val = data1;
15        next = NULL;
16    }
17    ListNode(int data1, ListNode *next1)
18    {
19        val = data1;
20        next = next1;
21    }
22};
23*/
24 
25class Solution {
26public:
27    ListNode* middleOfLinkedList(ListNode* head) {
28 
29    }
30};

Input:

Nums