143. Reorder List.md

143. Reorder List

---

leetcode Daily Challenge on August 20th, 2020.

leetcode-cn Daily Challenge on October 20th, 2020.

---

Difficulty : Medium

Related Topics : LinkedList

---

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

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

---

Solution

• Java
  • mine

    • LinkedList Runtime: 2 ms, faster than 41.50%, Memory Usage: 43.5 MB, less than 6.82% of Java online submissions

      // O(N)time 
      // O(N)space
      public void reorderList(ListNode head) {
          LinkedList<ListNode> list = new LinkedList<>();
          ListNode t = head;
          while(t!=null){
              list.add(t);
              t = t.next;
          }
          int index = 0;
          ListNode res = new ListNode();
          t = res;
          while(!list.isEmpty()){
              t.next = index % 2 == 0 ? list.pop() : list.removeLast();
              t = t.next;
              index++;
          }
          t.next = null;
          head = res.next;
      }
      

    • Runtime: 1 ms, faster than 99.93%, Memory Usage: 41.7 MB, less than 10.64% of Java online submissions

      // O(N)time
      // O(1)space
      public void reorderList(ListNode head) {
          while(head == null || head.next == null) return;
          ListNode fast = head;
          ListNode slow = head;
          while(fast != null && fast.next != null){
              fast = fast.next.next;
              slow = slow.next;
          }
          ListNode stop = slow;
          ListNode t = null;
          while(slow != null){
              ListNode temp = slow.next;
              slow.next = t;
              t = slow;
              slow = temp;
          }
          ListNode temp = head;
          while(t != null && temp != null){
              ListNode next = temp.next;
              temp.next = t;
              t = t.next;
              if(next == stop){
                  temp.next.next = t;
                  break;
              }else{
                  temp.next.next = next;
                  temp = temp.next.next;
              }
          }
      }
      

---

• the most votes

• Runtime: 1 ms, faster than 99.83%, Memory Usage: 42.5 MB, less than 6.82% of Java online submissions

  // O(N)time 
  // O(1)space
  public void reorderList(ListNode head) {
      if (head == null || head.next == null) return;
  
      //Find the middle of the list
      ListNode p1 = head;
      ListNode p2 = head;
      while (p2.next != null && p2.next.next != null) {
          p1 = p1.next;
          p2 = p2.next.next;
      }
  
      //Reverse the half after middle  1->2->3->4->5->6 to 1->2->3->6->5->4
      ListNode preMiddle = p1;
      ListNode preCurrent = p1.next;
      while (preCurrent.next != null) {
          ListNode current = preCurrent.next;
          preCurrent.next = current.next;
          current.next = preMiddle.next;
          preMiddle.next = current;
      }
  
      //Start reorder one by one  1->2->3->6->5->4 to 1->6->2->5->3->4
      p1 = head;
      p2 = preMiddle.next;
      while (p1 != preMiddle) {
          preMiddle.next = p2.next;
          p2.next = p1.next;
          p1.next = p2;
          p1 = p2.next;
          p2 = preMiddle.next;
      }
  }
  

---