Iterative 16ms C solution; 11 lines with comments


  • 0
    Z
    typedef struct ListNode ln;
    
    void reorderList(ln* head) {
      if(!head) return;
    
      int len = 0, idx = 0;         /* idx is the index of the stack */
      for(ln* tmp = head; tmp; tmp=tmp->next)   len++;
    
      ln *stack[len], *p;
      /* push all node pointers into the stack */
      for(p = head; p; p=p->next) stack[idx++] = p; 
    
      for(--idx; head != stack[idx] && head->next != stack[idx]; idx--)
      {
        /* the head of the list points to the top of the stack (i.e. the tail of the list) */
        p = head->next;
        head->next = stack[idx];
        head->next->next = p;
        head = p;
      }
      /* termintate the linked list */
      (stack[idx])->next = NULL;
    }

  • 1
    W

    You stored some nodes, so I dont think it is an in-place algorithm


  • 0
    Z

    @WTCCTW, thanks for your comments. The problem states: "You must do this in-place without altering the nodes' values." I think my solution can still be considered as in-place for two reasons. 1) I am not altering the value of any nodes. 2) The space complexity is much less than O(n), although not O(1), because I am not storing any node, I am storing the POINTERs (in a stack) to nodes, which usually have much smaller size than actually node struct in real world problems. Please let me know if my argument makes sense or not.


Log in to reply
 

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