Dummy Node小技巧：重排序一个给定链表
题目：给定一个链表和值x，重排序这个链表，使得小于x的值在大于等于x的值的前面。
分析：可以考虑先把小于x的值组成一个链表，大于等于x的值组成一个链表，然后再合并这两个链表即可。
那么这样的话，两个链表的头是不确定的，这个时候就自然要考虑用Dummy Node，由于是两个链表头，
所以用两个Dummy Node。代码如下：
ListNode *partition(ListNode *head,int val)
{//为空或者只有一个,那么直接返回原链表if(head == NULL || head->next == NULL)return head;ListNode *leftDummy = new ListNode(0);ListNode *rightDummy = new ListNode(0);ListNode *left = leftDummy;ListNode *right = rightDummy;ListNode *node = head;while(node != NULL){if(node->val < x){//left等于leftDummy的时候,那么下面第一句执行后表示leftDummy->next就是小值链表的头left->next = node;//left指向此刻小值链表的尾部left = left->next; }else{//right等于rightDummy的时候,那么下面第一句执行后表示rightDummy->next就是大值链表的头right->next = node;//right指向此刻大值链表的尾部right = right->next;}//node指向下一个节点node = node->next;}//小值链表的最后一个指向大值链表的头left->next = rightDummy->next;//大值链表的尾部指向NULLright->next = NULL;//返回小值链表的头return leftDummy->next;
}