Java Solution with 2 Loops


  • 0
    O
    1. Find the mid and do the reverse until mid. Careful on the old - even case.
    2. Reorder one item at time
        public void reorderList(ListNode head) {
            if (null == head){
                return;
            }
    
            ListNode prev = null;
            ListNode slow = head;
            ListNode fast = head;
    
            // find mid and do the rev until mid.
            while (null != fast && null != fast.next){
                fast = fast.next.next;
                ListNode n = slow.next;
                slow.next = prev;
                prev = slow;
                slow = n;
            }
    
            ListNode p = null;
    
            ListNode l1h = prev;
            ListNode l2h = slow;
            // if odd , then keep that mid node as the head;
            if (null != fast){
                p = l2h;
                l2h = l2h.next;
                p.next = null;
            }
    
            // reorder by picking one from each list.
            while (null != l1h &&  null != l2h ){
                ListNode l1hn = l1h.next;
                ListNode l2hn = l2h.next;
                l1h.next = l2h;
                l2h.next = p;
    
                p = l1h;
                l1h = l1hn;
                l2h = l2hn;
    
            }
    
            head = p;
        }
    
    
    

Log in to reply
 

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