cc150 2.4

partitionlist

#include<iostream>
using namespace std;
typedef struct node{
  int data;
  node *next;
}node; 
node *partitionlist(node *head, int x){
  node *dummy = new node();
  dummy->next=head;
  head=dummy;
  node *last=head;
  int len=0;
  if (head==NULL) return NULL;
  if (head->next==NULL) return head;
  while (last->next!=NULL) {
    last=last->next;
    ++len;
  }
  while (len>0){
    if (dummy->next->data >x ){
      node *q= dummy->next;
      dummy->next=dummy->next->next;
      dummy=dummy->next;
      last->next=q;
      q->next=NULL;
      last=last->next;
    }
    else {
      dummy=dummy->next;
      
    }
    len--;
  }
  return head->next;
}