LeetCode - Middle of the Linked List - 30Days Challenge

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.

Note:

The number of nodes in the given list will be between 1 and 100.

Solution

To get the middle element we need to require length of the LinkedList, Iterate over and calculate the length of the LinkedList. Divide it and iterate again till we reach to the middle element.

Code


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {
        
        int l=0,mid=0,tempMid=1;
        
        ListNode node=head;
        
        while(node!=null){
            l++;
            node=node.next;
        }
        
        mid=l/2;
        mid++;

        node=head;
        while(tempMid<mid){
            node=node.next;
            tempMid++;
        }
        
        return node;
    }
}