Reorder List

I solved one similar question before. That question is about reverse linked list, which is more difficult than this one. So this question does not take me much time. But at first, as I just want to test whether OJ system has restriction about time complexity on this problem, I did not use stack to store these nodes to be reordered. Instead, just use a loop to find the node, after which a new node should be inserted. No doubt, TLE, lol. Thus a stack is used. Sacrifice space for time. WAIT! The problem requires "in-place". Alright, solution 1 is NOT "in-place", while solution 2 is.

Solution 1 is quite straightforward, insert top element of stack after tmpPre node. Iterate above process until stack is empty. However, this solution needs extra space, i.e. O(n) space for stack. In solution 2, stack is abandoned.
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

// Solution 1
public class Solution {
    // Solution 1
    public void reorderList(ListNode head) {
        if(head == null || head.next == null || head.next.next == null) return;
        // Now the linked list is at least of length 3
        ListNode slow = head;
        ListNode fast = head;
     
        while(fast != null && fast.next != null ){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode copySlow = slow.next;
        LinkedList<ListNode> stack = new LinkedList<ListNode>();
        while(copySlow != null){// Use stack to store the nodes after slow, which will be inserted into the first //half of list
            stack.push(copySlow);
            copySlow = copySlow.next;
        }
        slow.next = null;
        ListNode tmpPre = head;
        while(!stack.isEmpty()){
            ListNode tmpNode = stack.pop();
            tmpNode.next = tmpPre.next;
            tmpPre.next = tmpNode;
            tmpPre = tmpPre.next.next;
        }
    }
}

For solution 2, at first, I have no idea how to deal with this question "in-place". After today's workout, I suddenly think of DFS while taking a shower. DFS can be implemented in 2 ways, recursively, or using a stack. This gives me the answer about how to solve this problem, yes, recursion! Start the recursion from node slow until we meet the end of list, then move end of the list after node tmpHead.  After each movement, tmpHead goes to the node right behind the newly inserted node, i.e. tmpHead = tmpHead.next.next .

One thing to notice is that if you want to keep the change of one passed-in object, like tmpHead here in one method, DO NOT make it void, make it the type of this object, and return that object as method finished.

//Solution 2

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        //Solution 2
        if(head == null || head.next == null || head.next.next == null) return;
        // Now the linked list is at least of length 3
        ListNode slow = head;
        ListNode fast = head;
     
        while(fast != null && fast.next != null ){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode preHalfHead = slow;
        ListNode tmpHead = head;
     
        // recursively insert the list node into first half of list
     
         reorderList(tmpHead, preHalfHead);
    }
 
    public ListNode reorderList(ListNode tmpHead, ListNode currentNode){
    if(currentNode.next == null) return tmpHead;
        tmpHead= reorderList(tmpHead,currentNode.next);
     
//        if(currentNode.next.next == null){
            currentNode.next.next = tmpHead.next;
            tmpHead.next = currentNode.next;
            currentNode.next = null;
         
            tmpHead= tmpHead.next.next;
            return tmpHead;
//        }
    }
}