5_5链表的分化

对于一个链表，我们需要用一个特定阈值完成对它的分化，使得小于等于这个值的结点移到前面，大于该值的结点在后面，同时保证两类结点内部的位置关系不变。

给定一个链表的头结点head，同时给定阈值val，请返回一个链表，使小于等于它的结点在前，大于等于它的在后，保证结点值不重复。

测试样例：
输入：{1,4,2,5},3
输出：{1,2,4,5}

/*
   struct ListNode {
   int val;
   struct ListNode *next;
   ListNode(int x) : val(x), next(NULL) {}
   };*/
class Divide {
    public:
        ListNode* listDivide(ListNode* head, int val) {
            // write code here
            if(NULL == head){
                return NULL;
            }
            ListNode *left_a = NULL, *right_a = NULL;
            ListNode *left_e = NULL, *right_e = NULL;
            // 如果小于就放到左边的链表，如果大于就放到右边的链表
            while(head != NULL){
                if(head->val <= val){
                    if(NULL == left_a){
                        left_a = head;
                        left_e = head;
                    }else{
                        left_e->next = head;
                        left_e = head;
                    }
                }else{
                    if(NULL == right_a){
                        right_a = head;
                        right_e = head;
                    }else{
                        right_e->next = head;
                        right_e = head;
                    }
                }
                head = head->next;
            }
            // 合并两个链表
            if(NULL != left_e){
                if(NULL != right_a){
                    left_e->next = right_a;
                    right_e->next = NULL;
                }
                //cout<< 1 << endl;
                return left_a;
            }else{
                //cout<< 2 << endl;
                return right_a;
            }
        }
};