My accepted Java solution in O(n)


  • 0
    R

    public class Solution {

    public void reorderList(ListNode head) {

      if ((head == null) || (head.next == null)) return; 
      ListNode middle;
      ListNode p1;
      ListNode p2;
      ListNode temp;
      ListNode middle_next;
      boolean even = false;
      
      middle = findMid(head);
      middle_next = middle.next;
      p1 = head;
      middle.next = null;
      p2 = reverseList(middle_next);
     
      
      while ((p1 != null) && (p2 != null)) {
        if (even == false) {
          temp = p1.next;    
          p1.next = p2;
          p1 = temp;
          even = !even;
        }
        else {
          temp = p2.next;    
          p2.next = p1;
          p2 = temp;
          even = !even;
        }
      }
    }
    
    private ListNode findMid(ListNode head) {
      ListNode slow = head;
      ListNode fast = head;
        
      while((fast.next != null) && (fast.next.next != null)) {
        slow = slow.next;    
        fast = fast.next.next;  
      }
      return slow;
    }
    
    private ListNode reverseList (ListNode head) {
      if(head.next == null) return head;    
      ListNode cur = head;
      ListNode next = head.next;
      ListNode next_next;
      
      while (next != null) {
        next_next = next.next;  
        if (cur == head)
          cur.next = null;
        next.next = cur;
        cur = next;
        next = next_next;
      }
      head = cur;
      return head;
      
    }
    

    }


  • 0
    G

    This version is easy to understand. I have some improvement. It is guaranteed that p1.length<=p2.length, we don't need to use boolean even, we can advance p1 and p2 in one iteration. Plus, we only need to check if(p1==null) then break.


Log in to reply
 

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