分隔链表
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例 :
输入: head = 1->4->3->2->5->2, x = 3
输出 : 1->2->2->4->3->5
思路：巧用临时头节点
*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {public:ListNode* partition(ListNode* head, int x) {ListNode less_head(0);ListNode more_head(0); //设置两个临时的头节点ListNode* less_ptr = &less_head; //对应指针指向这两个头节点ListNode* more_ptr = &more_head;while (head) { //如果节点值小于X，则将该节点插入less_ptr后if (head->val < x) {less_ptr->next = head;less_ptr = head; //链接完成后，less_ptr向后移动，指向head }else { //否则将该节点插入more_ptr后more_ptr->next = head;more_ptr = head;}head = head->next; //遍历链表}less_ptr->next = more_head.next; //将less链表尾，与more链表头相连more_ptr->next = NULL; //将more_ptr即链表节点next置空return less_head.next; //less_head的next节点即为新链表头节点，返回}
};