程序员面试金典 - 面试题 02.04. 分割链表

示例:
输入: head = 3->5->8->5->10->2->1, x = 5
输出: 3->1->2->10->5->5->8

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
    	ListNode *emptyHead = new ListNode(-1), *prev, *partTail;
    	emptyHead->next = head;
    	partTail = prev = emptyHead;
    	while(head)
    	{
    		if(head->val < x && partTail != prev)//注意第二个条件
    		{
    			prev->next = prev->next->next;//把head断开
    			head->next = partTail->next;//head接入小于x的段
    			partTail->next = head;//head接上前段尾巴
    			partTail = partTail->next;//更新尾巴，这句也可以不要
    			//不要的话，就是partTail其实是头，不变，一直往头上插入节点
    			head = prev->next;//更新head
    		}
    		else	//其他情况直接后移
    		{
    			prev = head;
    			head = head->next;
    		}
    	}
    	return emptyHead->next;
    }
};