[Java] Merging + Two Pointers solution with clear explanation and real life application. 🔥
Intuition\nThe problem "Reorder List" asks us to reorder a singly linked list such that it has a specific structures: the first node, followed by the last node,
# Intuition\nThe problem "Reorder List" asks us to reorder a singly linked list such that it has a specific structures: the first node, followed by the last node, then the second node, then the second-to-last node, and so on. \n\nThis problem is a combination and modification of these 3 problems: Middle of the Linked List, Reversed Linked List, Merge Sort. Here are the links to each:\n\n1. https://leetcode.com/problems/middle-of-the-linked-list/\n2. https://leetcode.com/problems/reverse-linked-list/\n3. https://leetcode.com/problems/merge-sorted-array/\n\n\nHere is the intuition behind this approach.\n\n1. Divide the linked list into two halves by finding the middle node using the slow-fast pointer technique.\n\n2. Reverse the second half of the list.\n\n3. Merge the two halves into a single sorted linked list.\n\n\n# Approach\nHere is the approach to this problem:\n\n1. Split the original list into two halves: We can split the list into two halves using the slow-fast pointer technique. This will give us two separate lists: the first half starts at the head of the original list and ends before the middle node, and the second half starts at the middle node and ends at the tail.\n\n2. Reverse the second half of the list: We need to reverse the second half of the list because we want to start with the last node and work our way towards the middle. \n\n3. Merge the two halves: After we have the two separate lists, we can merge them in the required order. We can do this by starting with the first node of the first list and the last node of the second list, then alternating between nodes from both lists until we reach the middle of the list.\n\n\n\n# Code\n```\nclass Solution {\n    public void reorderList(ListNode head) {\n        //find middle element\n        ListNode slow = head;\n        ListNode fast = head.next;\n        while(fast != null && fast.next != null)\n        {\n            slow = slow.next;\n            fast = fast.next.next;\n        }\n\n        //reverse the second half of the list starting from the middle\n        ListNode prev = null;\n        while(slow != null)\n        {\n            ListNode temp = slow.next;\n            slow.next = prev;\n            prev = slow;\n            slow = temp;\n        }\n\n        //Merge two halves\n        ListNode p1 = head;\n        ListNode p2 = prev;\n         while (p1 != null) {\n        ListNode next1 = p1.next;\n        ListNode next2 = p2.next;\n        p1.next = p2;\n        p2.next = next1;\n        p1 = next1;\n        p2 = next2;\n    }\n    }\n}\n```\n\n# Complexity\n- Time complexity: $$O(n)$$ where n is the length of the linked list. This is because we only need to traverse the list twice to find the middle node and reverse the second half of the list, and then traverse the list again to merge the two halves.\n\n- Space complexity: $$O(1)$$ because we only use a constant amount of extra space.\n\n# Application\nThe Reorder 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.*\n
['Linked List', 'Two Pointers', 'Java']