Beats 100% || Full Code Explained || [java/C++/C#/Python/JavaScript]
Intution\n1. We just need to know how to find middle of the linkedList, and reverse the linkedList.\n2. Now follow the visualization section, you will understan
# Intution\n1. We just need to know how to find middle of the linkedList, and reverse the linkedList.\n2. Now follow the visualization section, you will understand the whole process.\n\n# Visualization.\n1. ***Finding the middle of the LinkedList.***\n![e78d2d3a-5217-49f8-87e3-bc59c19070fc_1597916232.8641367.png](https://assets.leetcode.com/users/images/20c0435e-7277-4f13-a7a3-4e49f3866737_1711181311.417827.png)\n\n2. ***Reverse The Second Half.***\n![68bc80f5-630e-4c0a-a9da-605196a4e004_1597916252.5191195.png](https://assets.leetcode.com/users/images/b7d9cdb4-3850-4959-8e5d-6d23f9304515_1711181367.937276.png)\n\n3. ***Merge both the LinkedList.***\n![391f41fb-ed1f-4d67-a2f9-4d6aaf119214_1597916282.3228247.png](https://assets.leetcode.com/users/images/80919e49-429c-4b39-9663-a7cb05bf47cb_1711181461.5499132.png)\n\n\n# Approach\n### Step 1: Finding the Middle Node\n- The `midNode` function is used to locate the middle node of the linked list.\n- It utilizes the slow and fast pointer technique.\n- The slow pointer moves one step at a time while the fast pointer moves two steps at a time.\n- When the fast pointer reaches the end of the list, the slow pointer points to the middle node.\n\n### Step 2: Reversing the Second Half\n- After finding the middle node, the second half of the list starting from the node after the middle is reversed.\n- This is achieved using the `reverseLinkedList` function, which reverses the direction of the nodes in the second half of the list.\n\n### Step 3: Reordering the List\n- Once the list is divided and the second half is reversed, the `reorderList` function merges the two halves alternately.\n- Two pointers (`c1` and `c2`) are used to traverse the two halves simultaneously.\n- While both pointers are not null, nodes from each half are linked alternately.\n- Backup nodes are used to prevent losing the next nodes during reordering.\n- This process continues until all nodes are reordered.\n\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```Java []\nclass Solution {\n    public void reorderList(ListNode head) {\n        if(head==null || head.next==null) {\n            return;\n        }\n\n        ListNode middle = midNode(head);\n        ListNode newHead = middle.next;\n        middle.next = null;\n\n        newHead = reverseLinkedList(newHead);\n\n        ListNode c1 = head;\n        ListNode c2 = newHead;\n        ListNode f1 = null;\n        ListNode f2 = null;\n\n        while(c1 != null && c2 != null) {\n\n            // Backup\n            f1 = c1.next;\n            f2 = c2.next;\n\n            //Linking\n            c1.next = c2;\n            c2.next = f1;\n\n            // Move\n            c1 = f1;\n            c2 = f2;\n        }\n    }\n\n    private ListNode midNode(ListNode head) {\n        ListNode slow = head;\n        ListNode fast = head;\n\n        while(fast.next!=null && fast.next.next!=null) {\n            slow = slow.next;\n            fast = fast.next.next;\n        }\n        return slow;\n    }\n\n    private ListNode reverseLinkedList(ListNode head) {\n        ListNode prev = null;\n        ListNode curr = head;\n        ListNode forw = null;\n\n        while(curr != null) {\n            forw = curr.next;\n            curr.next = prev;\n            prev = curr;\n            curr = forw;\n        }\n        return prev;\n    }\n}\n```\n```C++ []\nclass Solution {\npublic:\n    void reorderList(ListNode* head) {\n        if (!head || !head->next) {\n            return;\n        }\n\n        ListNode* middle = midNode(head);\n        ListNode* newHead = middle->next;\n        middle->next = nullptr;\n\n        newHead = reverseLinkedList(newHead);\n\n        ListNode* c1 = head;\n        ListNode* c2 = newHead;\n        ListNode* f1 = nullptr;\n        ListNode* f2 = nullptr;\n\n        while (c1 && c2) {\n            // Backup\n            f1 = c1->next;\n            f2 = c2->next;\n\n            // Linking\n            c1->next = c2;\n            c2->next = f1;\n\n            // Move\n            c1 = f1;\n            c2 = f2;\n        }\n    }\n\nprivate:\n    ListNode* midNode(ListNode* head) {\n        ListNode* slow = head;\n        ListNode* fast = head;\n\n        while (fast->next && fast->next->next) {\n            slow = slow->next;\n            fast = fast->next->next;\n        }\n        return slow;\n    }\n\n    ListNode* reverseLinkedList(ListNode* head) {\n        ListNode* prev = nullptr;\n        ListNode* curr = head;\n        ListNode* forw = nullptr;\n\n        while (curr) {\n            forw = curr->next;\n            curr->next = prev;\n            prev = curr;\n            curr = forw;\n        }\n        return prev;\n    }\n};\n```\n```Python3 []\nclass Solution:\n    def reorderList(self, head: ListNode) -> None:\n        if not head or not head.next:\n            return\n\n        middle = self.midNode(head)\n        new_head = middle.next\n        middle.next = None\n\n        new_head = self.reverseLinkedList(new_head)\n\n        c1 = head\n        c2 = new_head\n        f1 = None\n        f2 = None\n\n        while c1 and c2:\n            # Backup\n            f1 = c1.next\n            f2 = c2.next\n\n            # Linking\n            c1.next = c2\n            c2.next = f1\n\n            # Move\n            c1 = f1\n            c2 = f2\n\n    def midNode(self, head: ListNode) -> ListNode:\n        slow = head\n        fast = head\n\n        while fast.next and fast.next.next:\n            slow = slow.next\n            fast = fast.next.next\n        return slow\n\n    def reverseLinkedList(self, head: ListNode) -> ListNode:\n        prev = None\n        curr = head\n\n        while curr:\n            forw = curr.next\n            curr.next = prev\n            prev = curr\n            curr = forw\n        return prev\n```\n```Go []\nfunc reorderList(head *ListNode) {\n    if head == nil || head.Next == nil {\n        return\n    }\n\n    middle := midNode(head)\n    newHead := middle.Next\n    middle.Next = nil\n\n    newHead = reverseLinkedList(newHead)\n\n    c1 := head\n    c2 := newHead\n    var f1, f2 *ListNode\n\n    for c1 != nil && c2 != nil {\n        // Backup\n        f1 = c1.Next\n        f2 = c2.Next\n\n        // Linking\n        c1.Next = c2\n        c2.Next = f1\n\n        // Move\n        c1 = f1\n        c2 = f2\n    }\n}\n\nfunc midNode(head *ListNode) *ListNode {\n    slow := head\n    fast := head\n\n    for fast.Next != nil && fast.Next.Next != nil {\n        slow = slow.Next\n        fast = fast.Next.Next\n    }\n    return slow\n}\n\nfunc reverseLinkedList(head *ListNode) *ListNode {\n    var prev, curr, forw *ListNode = nil, head, nil\n\n    for curr != nil {\n        forw = curr.Next\n        curr.Next = prev\n        prev = curr\n        curr = forw\n    }\n    return prev\n}\n```\n```C# []\npublic class Solution {\n    public void ReorderList(ListNode head) {\n        if (head == null || head.next == null) {\n            return;\n        }\n\n        ListNode middle = MidNode(head);\n        ListNode newHead = middle.next;\n        middle.next = null;\n\n        newHead = ReverseLinkedList(newHead);\n\n        ListNode c1 = head;\n        ListNode c2 = newHead;\n        ListNode f1 = null;\n        ListNode f2 = null;\n\n        while (c1 != null && c2 != null) {\n            // Backup\n            f1 = c1.next;\n            f2 = c2.next;\n\n            // Linking\n            c1.next = c2;\n            c2.next = f1;\n\n            // Move\n            c1 = f1;\n            c2 = f2;\n        }\n    }\n\n    private ListNode MidNode(ListNode head) {\n        ListNode slow = head;\n        ListNode fast = head;\n\n        while (fast.next != null && fast.next.next != null) {\n            slow = slow.next;\n            fast = fast.next.next;\n        }\n        return slow;\n    }\n\n    private ListNode ReverseLinkedList(ListNode head) {\n        ListNode prev = null;\n        ListNode curr = head;\n        ListNode forw = null;\n\n        while (curr != null) {\n            forw = curr.next;\n            curr.next = prev;\n            prev = curr;\n            curr = forw;\n        }\n        return prev;\n    }\n}\n```\n```JavaScript []\n/**\n * Definition for singly-linked list.\n * function ListNode(val, next) {\n *     this.val = (val===undefined ? 0 : val)\n *     this.next = (next===undefined ? null : next)\n * }\n */\n\n/**\n * @param {ListNode} head\n * @return {void} Do not return anything, modify head in-place instead.\n */\nvar reorderList = function(head) {\n    if (!head || !head.next) {\n        return;\n    }\n\n    const middle = midNode(head);\n    let newHead = middle.next;\n    middle.next = null;\n\n    newHead = reverseLinkedList(newHead);\n\n    let c1 = head;\n    let c2 = newHead;\n    let f1 = null;\n    let f2 = null;\n\n    while (c1 && c2) {\n        // Backup\n        f1 = c1.next;\n        f2 = c2.next;\n\n        // Linking\n        c1.next = c2;\n        c2.next = f1;\n\n        // Move\n        c1 = f1;\n        c2 = f2;\n    }\n};\n\nconst midNode = function(head) {\n    let slow = head;\n    let fast = head;\n\n    while (fast.next && fast.next.next) {\n        slow = slow.next;\n        fast = fast.next.next;\n    }\n    return slow;\n};\n\nconst reverseLinkedList = function(head) {\n    let prev = null;\n    let curr = head;\n    let forw = null;\n\n    while (curr) {\n        forw = curr.next;\n        curr.next = prev;\n        prev = curr;\n        curr = forw;\n    }\n    return prev;\n};\n```\n\n---\n\n### ***FEEL FREE TO GIVE SOME OTHER APROACHES, AND OPTIMIZE MY APPROACH***\n\n---\n\n![5c63d377-8ef4-4beb-b09d-0edb07e09a41_1702955205.6568592.png](https://assets.leetcode.com/users/images/1f85dd2b-3548-4bae-b6c4-9114a285e2f6_1711181931.5748205.png)\n
['Python', 'C++', 'Java', 'Go', 'Python3', 'JavaScript', 'C#']