题目
给定一个链表，给定一个target，讲链表中小于target的元素移至链表的前面，保持其余元素的相对位置不变
分析
举例分析：
输入：1->4->3->2->5->2 and x = 3,
输出：1->2->2->4->3->5
构建两个链表，链表1存储小于target的元素，链表2存储大于target的元素，最后将两个链表拼接
C++代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
/**
* 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) {
if(!head || !head->next) return head;
ListNode *p1, *p2;
ListNode tmp1(-1), tmp2(-1);
p1 = &tmp1, p2 = &tmp2;
while(head)
{
if(head->val < x){
p1->next = head;
p1 = p1->next;
}
else
{
p2->next = head;
p2 = p2->next;
}
head = head->next;
}
p2->next = NULL;
p1->next = tmp2.next;
return tmp1.next;
}
};
|
近期评论