Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
48 lines (41 sloc) 1.01 KB
problem:
Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.
---------------------------------------------------------------------------------
solution:
//逐个取当前结点,判断之后加入左或者右边列表,最后合并两个列表,将最后一个元素的next置为NULL。
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode *partition(ListNode *head, int x)
{
ListNode *pL = NULL;
ListNode *pR = NULL;
ListNode **ppL = &pL;
ListNode **ppR = &pR;
ListNode *pLast = NULL;
while(head)
{
if(head->val < x)
{
*ppL = head;
ppL = &(head->next);
}
else
{
*ppR = head;
ppR = &(head->next);
pLast = head;
}
head = head->next;
}
*ppL = pR;
if(pLast)
pLast->next = NULL;
return pL;
}