Explained With Images. 1ms Solution. Beats 99%.
Approach\n\nThis Problem can be divided into three sub parts \n\n 1. https://leetcode.com/problems/middle-of-the-linked-list/description/\n 2. https://leetcode.
# Approach\n\nThis Problem can be divided into three sub parts \n\n 1. https://leetcode.com/problems/middle-of-the-linked-list/description/\n 2. https://leetcode.com/problems/reverse-linked-list/description/\n 3. Merge two lists, which we will discover in this problem.\n\nWe need to perform the in-place reversal for the second half of the linked list, which will allow us to not use any extra memory. To solve the original problem, we can use the modified in-place methodology after the first in-place reversal to merge the two halves of the linked list. We can use two-pointers, first and second, to point to the heads of the two halves of the linked list. We\u2019ll traverse both halves in lockstep to merge the two linked lists, interleaving the nodes from the second half into the first half.\n\n## Below are the illustrations to help you understand better :\n\n![Screenshot 2024-08-11 at 10.23.49\u202FAM.png](https://assets.leetcode.com/users/images/58cb32f2-d939-4bea-8777-3f0401bb0e8f_1723386465.541971.png)\n![Screenshot 2024-08-11 at 10.23.54\u202FAM.png](https://assets.leetcode.com/users/images/95eb18ee-4f69-49b4-b689-1667474c6f61_1723386468.6040862.png)\n![Screenshot 2024-08-11 at 10.23.58\u202FAM.png](https://assets.leetcode.com/users/images/3b1b9dfe-c857-44cd-87c9-6825f71aa490_1723386471.1056218.png)\n![Screenshot 2024-08-11 at 10.24.01\u202FAM.png](https://assets.leetcode.com/users/images/f659d79d-25c5-4add-a44b-b2107610674a_1723386473.188124.png)\n![Screenshot 2024-08-11 at 10.24.03\u202FAM.png](https://assets.leetcode.com/users/images/76033161-878d-4a32-9a07-c21ae31b299e_1723386475.7863505.png)\n\n\n# Complexity\n- Time complexity:\nThe time complexity of this solution is linear, $$O(n)$$\n\n- Space complexity:\nThe space complexity of the solution is constant, $$O(1)$$\n\n# Code\n```\nclass Solution {\n    public void reorderList(ListNode head) {\n        \n      \tif(head == null)\n\t\t    return head;\n\t\t// find the middle of linked list\n\t\t// in 1->2->3->4->5->6 find 4 \n\t\tLinkedListNode slow = head; \n\t\tLinkedListNode fast = head;\n\n\t\twhile(fast!= null && fast.next != null)\n\t\t{\n\t\t\tslow = slow.next;\n\t\t\tfast = fast.next.next;\n\t\t}\n\t\t// reverse the second part of the list\n        // convert 1->2->3->4->5->6 into 1->2->3 and 6->5->4\n        // reverse the second half in-place\n\t\tLinkedListNode prev = null;\n\t\tLinkedListNode curr = slow;\n\t\tLinkedListNode next = null;\n\n\t\twhile(curr != null)\n\t\t{\n\t\t\tnext = curr.next;\n\t\t\tcurr.next = prev;\n\t\t\tprev = curr;\n\t\t\tcurr = next;\n\t\t}\n\t\t// merge two sorted linked lists\n        // merge 1->2->3 and 6->5->4 into 1->6->2->5->3->4\n\t\tLinkedListNode first = head;\n\t\tLinkedListNode second = prev;\n\t\tLinkedListNode temp = head;\n\n        while(second.next != null)\n\t\t{\n\t\t\ttemp = temp.next;\n\t\t\tfirst.next = second;\n\t\t\tsecond = second.next;\n\t\t\tfirst.next.next = temp;\n\t\t\tfirst = first.next.next;\n\t\t}\n\n\t\treturn head;\n}\n}\n```\n\n![Screenshot 2024-08-11 at 10.28.30\u202FAM.png](https://assets.leetcode.com/users/images/b1b69b0e-e7d1-40dd-8ae2-f3fe0d8932bd_1723386524.0506632.png)\n
['Linked List', 'Two Pointers', 'C++', 'Java', 'Python3']