给定一个单链表和数值x，划分链表使得所有小于x的节点排在大于等于x的节点之前。 你应该保留两部分内链表节点原有的相对顺序。 样例: 给定链表 1->4->3->2->5->2->null，并且 x=3 返回 1->2->2->4->3->5->null
#ifndef C96_H #define C96_H #include<iostream> using namespace std; class ListNode{ public: int val; ListNode *next; ListNode(int val) { this->val = val; this->next = NULL; } }; class Solution { public: /** * @param head: The first node of linked list. * @param x: an integer * @return: a ListNode */ ListNode *partition(ListNode *head, int x) { // write your code here ListNode *p = head, *preHead=new ListNode(0), *postHead=new ListNode(0); ListNode *pre = preHead, *post = postHead; while (p != NULL) { ListNode *next = p->next; if (p->val >= x) { post->next=p; post = post->next; post->next = NULL; } else { pre->next = p; pre = pre->next; pre->next = NULL; } p = next; } pre->next = postHead->next; return preHead->next; } }; #endif