Leetcode：Partition List

Given a linked list and a valuex, partition it such that all nodes less thanxcome before nodes greater than or equal tox.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,Given1->4->3->2->5->2andx= 3,

return1->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 node1(0), node2(0);ListNode *p1 = &node1, *p2 = &node2;while (head) {if (head->val < x)p1 = p1->next = head;elsep2 = p2->next = head;head = head->next;}p2->next = NULL;p1->next = node2.next;return node1.next;}};

既有美妙的风景，也会有称不上景、只有风的地方。