一次过，链表题无难度
1
/*
*
2
* Definition for singly-linked list.
3
* struct ListNode {
4
* int val;
5
* ListNode *next;
6
* ListNode(int x) : val(x), next(NULL) {}
7
* };
8
*/
9
class
Solution {
10
public
:
11
ListNode *partition(ListNode *head,
int
x) {
12
//
Start typing your C/C++ solution below
13
//
DO NOT write int main() function
14
ListNode *less, *larger, *p, *q, *
ret;
15
less = larger = p = q = ret =
NULL;
16
while
(head) {
17
if
(head->val <
x) {
18
if
(!
less) {
19
less =
new
ListNode(head->
val);
20
p =
less;
21
}
22
else
{
23
p->next =
new
ListNode(head->
val);
24
p = p->
next;
25
}
26
}
27
else
{
28
if
(!
larger) {
29
larger =
new
ListNode(head->
val);
30
q =
larger;
31
}
32
else
{
33
q->next =
new
ListNode(head->
val);
34
q = q->
next;
35
}
36
}
37
head = head->
next;
38
}
39
if
(!less) ret =
larger;
40
if
(!larger) ret =
less;
41
if
(less &&
larger) {
42
p->next =
larger;
43
ret =
less;
44
}
45
return
ret;
46
}
47
};
C#
1
/*
*
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* public int val;
5
* public ListNode next;
6
* public ListNode(int x) { val = x; }
7
* }
8
*/
9
public
class
Solution {
10
public
ListNode Partition(ListNode head,
int
x) {
11
ListNode less =
null
, larger =
null
, p =
null
, q =
null
, ans =
null
;
12
while
(head !=
null
) {
13
if
(head.val <
x) {
14
if
(less ==
null
) {
15
less =
new
ListNode(head.val);
16
p =
less;
17
}
18
else
{
19
p.next =
new
ListNode(head.val);
20
p =
p.next;
21
}
22
}
23
else
{
24
if
(larger ==
null
) {
25
larger =
new
ListNode(head.val);
26
q =
larger;
27
}
28
else
{
29
q.next =
new
ListNode(head.val);
30
q =
q.next;
31
}
32
}
33
head =
head.next;
34
}
35
if
(less ==
null
) ans =
larger;
36
if
(larger ==
null
) ans =
less;
37
if
(less !=
null
&& larger !=
null
) {
38
p.next =
larger;
39
ans =
less;
40
}
41
return
ans;
42
}
43
}
