[Java, Rust, Python] Two Pointers solution with clear explanation and real life application. 🔥
Intuition\n Describe your first thoughts on how to solve this problem. \nThe problem "Middle of the Linked List" asks us to find the middle node of the linked l
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe problem "Middle of the Linked List" asks us to find the middle node of the linked list. The intuition behind this problem is to use two pointers - a slow pointer and a fast pointer - to traverse the list.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe first initialized the slow pointer and the fast pointer to point to the head of the linked list. For each iteration, the slow pointer moves one node and the fast pointer moves 2 nodes. \n\nBy the time the fast pointer reaches the end of the list, the slow pointer will be pointing to the middle node.\n\n# Code\n``` java []\nclass Solution {\n    public ListNode middleNode(ListNode head) {\n        ListNode slow = head;\n        ListNode fast = head;\n\n        while(fast != null && fast.next != null)\n        {\n            slow = slow.next;\n            fast = fast.next.next;\n        }\n\n        return slow;\n    }\n}\n```\n``` python []\nclass Solution(object):\n    def middleNode(self, head):\n        """\n        :type head: ListNode\n        :rtype: ListNode\n        """\n        slow  = head\n        fast = head\n\n        while fast and fast.next:\n            slow = slow.next\n            fast = fast.next.next\n\n        return slow\n```\n``` rust []\nimpl Solution {\n    pub fn middle_node(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {\n        let mut slow = &head;\n        let mut fast = &head;\n        \n        while fast.is_some() && fast.as_ref().unwrap().next.is_some() {\n            slow = &slow.as_ref().unwrap().next;\n            fast = &fast.as_ref().unwrap().next.as_ref().unwrap().next;\n        }\n        return slow.clone();\n    }\n}\n```\n\n\n# Complexity\n- Time complexity: $$O(n)$$ where n is the number of nodes in the linked list.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$ because we use a constant amount of extra space to perform the search.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n\n# Application\nThe Middle of the Linked List problem have several real-life applications:\n\n1. **Browser Hsitory**: a browser history is typically implement using a linked list data structure, where each webpage visited is stored as a node in the list.\n\n2. **Music Playlists**: each song is stored as a node in the list, and the order of songs in the playlist is determined by the order of nodes in the list.\n\n3. **File systems:** a file system is usually organized as a hierarchy of directories and files. Each directory and file can be represented as a node in a linked list, with a pointer to its parent directory and a list of child nodes.\n\n4. **LRU Cache:** a LRU (Least Recently Used) cache is common caching stategy used in computer systems to store recently accessed items.\n\n5. **Garbage collection**: implmented using a linked list of objects that are no longer in use called "free list". The garbage colletor scans this list periodically to free up memory.\n\n\n5. **Image manipulation**: represent images as a set of pixels. Each pixel is stored as a node in the list, with a pointer to its neighboring pixels.\nThis allow for efficient image manipulation, such as scaling or cropping.\n\n*Thank you for reading! If you found this solution helpful, please give me an upvote. Feel free to add suggestions.*
['Linked List', 'Two Pointers', 'Python', 'Java', 'Rust']