Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

Solution:
Linked List implementation question.
1. cut off the linked list in the middle.
2. reverse the right half linked list. (insert the new node at the beginning)
3. insert the right half into the left half.

public class Solution {
    public void reorderList(ListNode head) {
        // corner case
        if(head == null || head.next == null)
            return;
        
        // cut off the list in the middle
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode cur = slow.next;
        slow.next = null;
        
        // reverse the right part
        ListNode dummy = new ListNode(0);
        while(cur != null){
            ListNode nt = cur.next;
            
            cur.next = dummy.next;
            dummy.next = cur;
            
            cur = nt;
        }
        
        // combine two parts
        ListNode left = head;
        ListNode right = dummy.next;
        ListNode left_nt = null;
        ListNode right_nt = null;
        while(right != null){
            left_nt = left.next;
            right_nt = right.next;
            
            left.next = right;
            right.next = left_nt;
            
            left = left_nt;
            right = right_nt;
        }
        
    }
}