题目描述
给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。 你应当保留两个分区中每个节点的初始相对位置。 示例: 输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5
通过的代码
class Solution {
public:
ListNode
* partition(ListNode
* head
, int x
) {
ListNode
* LeftHead
=new ListNode(-1);
ListNode
* RightHead
=new ListNode(-1);
ListNode
* NewHead
=LeftHead
;
ListNode
* NextHead
=RightHead
;
if(head
==NULL)
return NULL;
while(head
)
{
if(head
->val
<x
)
{
LeftHead
->next
=head
;
LeftHead
=LeftHead
->next
;
}
else
{
RightHead
->next
=head
;
RightHead
=RightHead
->next
;
}
head
=head
->next
;
}
RightHead
->next
=NULL;
LeftHead
->next
=NextHead
->next
;
return NewHead
->next
;
}
};
解题思路
这个题目还是考察链表，考察对于链表指针的熟悉和使用。其实只要把思路想清楚了，这道题目就很简单。光看题目可能会难以准确理解题意，但是结合例子看就很清楚了。从例子可以看到，新的链表其实就是把所有小于x的链表结点按照原来链表的先后顺序连接在左侧，把所有大于x的链表结点按照原来链表的先后顺序连接在右侧。要实现这一点，肯定需要同时构建两个链表（如果只构建一个链表，是无法实现这一点的）。一个链表用来构建左侧小于x的链表，另一个链表用来构建右侧大于x的链表。构建一个循环，对于原来链表的所有结点与x进行大小的比较，来决定这个结点的存放位置（放在左侧的链表还是右侧的链表），最后再将两个链表连接在一起，得到的就是我们需要返回的新的链表。
