題目：給定一個鏈表和一個數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)。多學一個知識點了。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
