Leetcode: Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

-----------------------------------------

-----------------------------------------

Using two pointers. 

Note this coommand:  while (p->next != NULL && p->next->val<x), the "p->next != NULL" judgement should be put in front of "p->next->val<x". 

///////////////////////////////////////////////////

//code

class Solution {

public:

       ListNode* partition(ListNode* head, int x) {

              //check input

              if (head == NULL)return head;

              //dummy head

              ListNode *dum = new ListNode(-1);

              dum->next = head;

              ListNode  *tmp = head, *p = dum, *f = dum;

              //locate the first node>x

              while (p->next != NULL && p->next->val<x)p = p->next;

              if (p->next == NULL)return head;

              f = p->next;

              //find node <x

              while (f->next != NULL){

                     if (f->next->val<x){

                           tmp = p->next;

                           p->next = f->next;

                           f->next = f->next->next;

                           p->next->next = tmp;

                           p = p->next;

                     }

                     else f = f->next;

              }

              head = dum->next;

              delete dum;

              return head;

       }

};