leetcode：Partition List （链表处理）【面试算法题】
题目：
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.
题意求一个新的链表，满足原链表比x小的数在左边，比x大的数在右边，他们之间的相对顺序不变。
先创建两个链表，分别存比x小的链表和比x大的链表，最后吧两个链表链接起来。
/** * 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 *head1,*head2,*p1,*p2; head1=new ListNode(0); head2=new ListNode(0); p1=head1; p2=head2; while(head!=NULL) { if(head->val<x) { p1->next=new ListNode(head->val); p1=p1->next; } else { p2->next=new ListNode(head->val); p2=p2->next; } head=head->next; } if(head2->next!=NULL)p1->next=head2->next; ListNode *temp=head1->next; delete(head1); delete(head2); return temp; }};//http://blog.csdn.net/havenoidea