Lintcode 链表划分
程序员文章站
2022-03-24 17:44:08
...
题目描述:
给定一个单链表和数值x,划分链表使得所有小于x的节点排在大于等于x的节点之前。你应该保留两部分内链表节点原有的相对顺序。
解释:
本道题目我的解法是先遍历链表,对于小于x的节点数据域压入pre数组中,其余节点数据域压入last数组,然后将pre和last分别顺序不变压入result数组中,最后再遍历链表,将链表中的每一个节点的数据域重新赋值为result数组中的数值。
代码:
class Solution {
public:
/**
* @param head: The first node of linked list
* @param x: An integer
* @return: A ListNode
*/
ListNode * partition(ListNode * head, int x) {
// write your code here
if(head==NULL)
{
return NULL;
}
vector<int>pre;
vector<int>last;
vector<int>result;
ListNode *ptemp = head;
while(ptemp!=NULL)
{
if(ptemp->val < x)
{
pre.push_back(ptemp->val);
}
else
{
last.push_back(ptemp->val);
}
ptemp = ptemp->next;
}
result.insert(result.end(),pre.begin(),pre.end());
result.insert(result.end(),last.begin(),last.end());
ListNode *temp = head;
int i = 0;
while(temp!=NULL)
{
temp->val= result[i];
i++;
temp = temp->next;
}
return head;
}
};
运行结果:
补充:
vector insert() 函数有以下三种用法:
- 在指定位置loc前插入值为val的元素,返回指向这个元素的迭代器,
- 在指定位置loc前插入num个值为val的元素
- 在指定位置loc前插入区间[start, end)的所有元素 .
例如:
v.insert(v.begin(),8);//在最前面插入新元素。
v.insert(v.begin()+2,1);//在迭代器中第二个元素前插入新元素 。
v.insert(v.end(),3);//在向量末尾追加新元素。
v.insert(value.begin(), 4, 2);//在向量前面插入4个2。
result.insert(result.end(),pre.begin(),pre.end());//在向量result末尾插入pre向量区间内元素。