Java Solution in three parts


  • 0
    1. find the middle one to break the LinkedList
    2. reverse the second part
    3. restructure the LinkedList
        public void reorderList(ListNode head) {  
            
            if (head == null || head.next == null) {
                return;
            }
            
            ListNode fast = head, slow = head;
            while (fast.next != null && fast.next.next != null) {
                fast = fast.next.next;
                slow = slow.next;
    
            }
            // now slow is the mid, reverse from slow->next to end
    
            ListNode prev = null;
            ListNode curt = slow.next;
            // break the connection
            slow.next = null;
            
            while (curt != null) {
                ListNode temp = curt.next;
                curt.next = prev;
                prev = curt;
                curt = temp;
            }
            
            // Ln starts from prev, L0 starts from head
            curt = new ListNode(-1);
            ListNode temp = head;
            
            while(prev != null) {
                curt.next = temp;
                temp = temp.next;
                curt = curt.next;
                curt.next = prev;
                prev = prev.next;
                curt = curt.next;
            }
            
            if (temp != null) {
                curt.next = temp;
            }
    
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.