链表分化问题

链表分化问题为给定一个阈值，使得小于等于这个阈值的结点移到前面，大于这个阈值的结点移到后面，同时保证两类结点的内部位置关系不变。

思路一：把链表元素放到数组中，利用快排思想进行排序，类似荷兰国旗问题，但因为涉及到交换，不能保证同一类结点内部位置关系不变。

思路二：将小于等于这个阈值的结点生成一个链表，大于这个阈值的结点生成一个链表，最后将两个链表连在一起即可。

注意事项：

1、每个链表保存好head和tail指针，以便首尾连接。

2、遍历到原链表中的某一结点时，先保存该结点的next值（后续结点），再将该结点从原链表断开（设置next值为0）。注意一定要将结点从原始链表中断开，否则新链表中会存储该结点的后续结点信息。

代码实现：

/*
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 (head == NULL || head->next == NULL)
			return head;

		ListNode *head1 = NULL;
		ListNode *tail1 = NULL;
		ListNode *head2 = NULL;
		ListNode *tail2 = NULL;
		ListNode *next = head;
		while (head != NULL) {
			next = head->next;// next 存储后续结点
			head->next = NULL;//必须将当前结点断开，不然该结点的后续结点信息也会保存到新链表中去
			if (head->val <= val)//小于等于的链表
			{
				if (head1 == NULL)
				{
					head1 = head;
					tail1 = head;
				}
				else {
					tail1->next = head;
					tail1 = head;
				}
			}
			else {
				if (head2 == NULL) {
					head2 = head;
					tail2 = head;
				}
				else {
					tail2->next = head;
					tail2 = head;
				}
			}

			head = next;
		}
		if (head1 != NULL) {
			tail1->next = head2;
			return head1;
		}
		else
			return head2;


	}
};