Java solution with 3 steps


  • 29
      public class Solution {
        
        public void reorderList(ListNode head) {
          if (head == null || head.next == null)
              return;
          
          // step 1. cut the list to two halves
          // prev will be the tail of 1st half
          // slow will be the head of 2nd half
          ListNode prev = null, slow = head, fast = head, l1 = head;
          
          while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
          }
          
          prev.next = null;
          
          // step 2. reverse the 2nd half
          ListNode l2 = reverse(slow);
          
          // step 3. merge the two halves
          merge(l1, l2);
        }
        
        ListNode reverse(ListNode head) {
          ListNode prev = null, curr = head, next = null;
          
          while (curr != null) {
            next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
          }
          
          return prev;
        }
        
        void merge(ListNode l1, ListNode l2) {
          while (l1 != null) {
            ListNode n1 = l1.next, n2 = l2.next;
            l1.next = l2;
            
            if (n1 == null)
              break;
                
            l2.next = n1;
            l1 = n1;
            l2 = n2;
          }
        }
    
      }

  • 1
    L

    same idea :) And at first I used recursion version for reverse list function and got stack over flow error. This didn't happen in the simple problem of reverse list in leecode. It's weird.


  • 0
    B

    I got Memory Limit problem in merge part. I don't know why.

    while(second !=null && first!=null ){

    ListNode temp1 = first.next;

    ListNode temp2 = second.next;

    first.next = second;

    if(temp1 == null) break;

    second.next = temp1;

    first = temp1;

    second = temp2;
    }


Log in to reply
 

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