题目：给定一个链表和一个数x，将链表中比x小的放在前面，其他的放在后头。例如：
Given
1->4->3->2->5->2
and
x
= 3,
return
1->2->2->4->3->5
.
思路：
1. 再用两个node，一个指向所有小于x的，一个指向其他的，之后把两个接在一起。接在一起需要注意large是否未移动过。
/*
*
* 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 == NULL || head -> next == NULL)
return
head;
ListNode
*ans_small =
new
ListNode(
0
);
// 存小于x的
ListNode
*ans_large =
new
ListNode(
0
);
// 存不小于x的
ans_small
-> next =
head;
ans_large
-> next =
head;
ListNode
*small =
ans_small;
ListNode
*large =
ans_large;
ListNode
*cur =
head;
while
(cur)
{
if
(cur -> val <
x)
{
small
-> next =
cur;
small
=
cur;
cur
= cur ->
next;
}
else
{
large
-> next =
cur;
large
=
cur;
cur
= cur ->
next;
}
}
large
-> next = NULL;
//
这个是为了防止large指向head的时候
small -> next = ans_large ->
next;
head
=
ans_small;
delete ans_small, ans_large;
return
head ->
next;
}
};
2. 就创建一个node，这个node遇见比x小的就插入
class
Solution {
public
:
ListNode
*partition(ListNode *head,
int
x)
{
if
(head == NULL || head -> next == NULL)
return
head;
ListNode
*ans =
new
ListNode(
0
);
ans
-> next =
head;
ListNode
*small = ans;
//
在它的后面插入小的
ListNode *cur =
head;
ListNode
*pre = ans;
//
cur的前一个指针，方便插入操作
bool
flag =
true
;
//
true说明要插入的紧接着就是下一个，那就不用插入，加加就好
while
(cur !=
NULL)
{
if
(cur -> val < x && small -> next == cur)
//
待插入的和之前小的相邻就不用插入了
{
pre
= pre ->
next;
cur
= cur ->
next;
small
= small ->
next;
}
else
if
(cur -> val < x && small -> next != cur)
//
不相邻，插入
{
ListNode
*tmpnext = small ->
next;
small
-> next =
cur;
small
=
cur;
cur
= cur ->
next;
small
-> next =
tmpnext;
pre
-> next =
cur;
flag
=
true
;
}
else
if
(cur -> val >=
x)
{
flag
=
false
;
cur
= cur ->
next;
pre
= pre ->
next;
}
}
head
=
ans;
delete ans;
return
head ->
next;
}
};
从第二个思路中知道了原来可以判断连个node是否相等！这个之前以为不能那样判断的，原来可以用 if(node1 == node2)。多学一个知识点了。
