Nowcoder rearrange linked list

Ideas

stay $O(n)$ Under the space complexity requirements of , It's easy to think of using a sequence table to store all nodes .
If the space complexity is $O(1)$:

1. Use the speed pointer to find the intermediate node .
2. Reverse the second half of the list
3. Merge two linked lists

Code

    ListNode reverseList(ListNode head){
    
        if(head == null || head.next == null) {
    
            return head;
        }
        ListNode reverse = reverseList(head.next);
        head.next.next= head;
        head.next = null;
        
        return reverse;
    }
    
    public void reorderList(ListNode head) {
    
        ListNode fast = head;
        ListNode slow = head;
        while(fast.next!=null && fast.next.next!=null) {
    
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode rrh = reverseList(slow.next);
        slow.next = null;
        ListNode lh = head;
        while(rrh!=null) {
    
            ListNode rrh_next = rrh.next, lh_next = lh.next;
            rrh.next = lh.next;
            lh.next = rrh;
            lh = lh_next;
            rrh = rrh_next;
        }
    }