[C++/JAVA] EASY TO SOLVE || Different Variations with detailed explanations
Brute Force approach || Tortoise and Hare approach\n\nwe need to find the middle node of the given linkedlist . In case of even number of nodes in the linkedlis
# **Brute Force approach || Tortoise and Hare approach**\n\nwe need to find the middle node of the given linkedlist . In case of even number of nodes in the linkedlist the 2nd middle node is the favourable output .\n\n**Intuition:-**\n* Since we need to find the middle node of the linked list , The best intuition we can get is to traverse the whole linkedlist and once we find the length of the linkedlist we can easily **find middle node by dividing the length with 2** `i.e middleNode= Length of LinkedList / 2 ` \n* There is one more method to solve this question as well .The name of that method is **Tortoise and hare method or slow and fast pointer approach or two pointer approach** .In this method we take two pointer one as slow and other as fast . The Slow pointer moves by one step whereas fast moves by 2 steps. By the time fast reaches the end of the LinkedList, slow pointer will reach to the middle node \n\n**Brute Force Algorithm :-**\n1. Initialize a pointer `temp` which will traverse the whole linkedlist and find the `length` of the linkedlist .\n2. Now initialize a another variable known as `middle` for finding the middle node as MiddleNode will be equal to `Middle Node= Length of LinkedList / 2` \n3. Once we get the index of the middle Node then we need to travers our temp pointer back to that middeNode to know the value of middle node\n\n**C++ Brute Force Code:-**\n```\nclass Solution {\npublic:\n    ListNode* middleNode(ListNode* head) {\n        ListNode *temp = head;\n        int length=0;\n\t\t\t\t//Traversing temp till the end of linked list to find length #O(n)\n        while(temp){\n            length++;\n            temp = temp->next;\n        }\n        int middle = length/2;\n        temp=head;\n       //traversing temp node back to middle node #O(n/2)\n        while(temp && middle--)\n            temp=temp->next;\n        \n        return temp;\n    }\n};\n```\n**JAVA Brute Force Code:-**\n```\nclass Solution {\n    public ListNode middleNode(ListNode head) {\n        ListNode temp = head;\n        int length=0;\n\t\t//Traversing temp till the end of linked list to find length #O(n)\n        while(temp!=null){\n            temp = temp.next;\n            length++;\n        }\n        int middle = length/2;\n        temp=head;\n        //traversing temp node back to middle node #O(n/2)\n        while(middle != 0){                \n         temp = temp.next;\n         middle--;\n        }\n        return temp;\n    }\n}\n```\n**Time Complexity:** *`O(N)+O(N/2) = O(N)`*\n**Space Complexity:** *`O(1)`*\n\n**Two Pointer Algortihm or Tortoise and Hare Algorithm :**\n1. Initialize the two pointers `slow` and `fast` at the head of linked list .\n2. Now every time, slow moves 1 step at a time while fast is moves 2 steps at a time. When fast pointer arrives at the end, slow pointer will arrive right in the middle of our linked list.\n3. Now just return the value of slow pointer .\n\n**C++ CODE:-**\n```\nclass Solution {\npublic:\n        ListNode* middleNode(ListNode* head) {\n        ListNode *slow = head, *fast = head;\n        while (fast && fast->next)\n            slow = slow->next, fast = fast->next->next;\n        return slow;\n    }\n};\n```\n**JAVA CODE:-**\n```\nclass Solution {\n    public ListNode middleNode(ListNode head) {\n        ListNode slow = head, fast = head;\n\t\t// slow moving 1 step at a time while fast is moving 2 steps at a time #O(N/2)\n        while (fast != null && fast.next != null) {\n            slow = slow.next;\n            fast = fast.next.next;\n        }\n        return slow;\n    }\n}\n```\n**Time Complexity:** *`O(N/2)=O(N)`*\n**Space Complexity:** *`O(1)`*\n
['Linked List', 'Two Pointers', 'C', 'C++']