欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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;
    }
};

运行结果:
Lintcode 链表划分


补充:

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向量区间内元素。

相关标签: 算法 链表