Simple C++ solution, O(n) ans O(1) space


#1

/**

  • Definition for singly-linked list.

  • struct ListNode {

  • int val;
    
  • ListNode *next;
    
  • ListNode(int x) : val(x), next(NULL) {}
    
  • };
    /
    ListNode
    Solution::solve(ListNode* a){
    ListNode *temp=a,*last=a,*stop,*Next,*pre,*end,*head=a;
    while(temp){
    last=temp;
    temp=temp->next;
    }
    stop=last;
    temp=a;
    pre=NULL;
    end=a;
    Next=a;
    while(temp && stop!=temp){
    end=temp;
    if(temp->val==1){
    Next=end->next;
    end->next=NULL;
    last->next=end;
    last=end;
    if(!pre){
    head=Next;
    }
    else
    pre->next=Next;
    temp=Next;
    }
    else{
    pre=temp;
    temp=temp->next;
    }

    }
    return head;
    }