Simple O(n) similar to odd and even nodes


#1

/**

  • Definition for singly-linked list.
  • struct ListNode {
  • int val;
    
  • ListNode *next;
    
  • ListNode(int x) : val(x), next(NULL) {}
    
  • };
    /
    ListNode
    Solution::partition(ListNode* A, int B)
    {
    ListNode*start=NULL, *less=NULL, *more=NULL, *connect=NULL, *iter=A;
    while(iter!=NULL)
    {
    if(iter->val<B)
    {
    if(less==NULL)
    {
    start=iter;
    less=iter;
    }
    else
    {
    less->next=iter;
    less=less->next;
    }
    }
    else
    {
    if(more==NULL)
    {
    more=iter;
    connect=iter;
    }
    else
    {
    more->next=iter;
    more=more->next;
    }
    }
    iter=iter->next;
    }
    if(less==NULL) return connect;
    less->next=connect;
    more->next=NULL;
    return start;
    }.