温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

Partition List

发布时间:2020-07-18 01:41:23 来源:网络 阅读:401 作者:程红玲OOO 栏目:编程语言

描述

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater

than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.


partition_list.h

#include <iostream>
#include <assert.h>
#include <stdlib.h>

using namespace std;

typedef struct ListNode {
    int _val;
    ListNode *_next;
    ListNode(int x) : _val(x), _next(NULL)
    {}  
}node,*node_p;

class Solution
{
public:
    node_p partition(node_p &list,int x)
    {   
        //参数检查
        if(list==NULL)
            return NULL;
     
        node dummy(-1);
        node_p head=&dummy;
        head->_next=list;
        
        node_p first=head;
        
        //找_val为x的结点
        node_p node_x=list;
        while(node_x!=NULL && node_x->_val!=x){
            node_x=node_x->_next;
            first=first->_next;
        }
        if(node_x==NULL){
            cout<<"not find node_x!"<<endl;
            return list;
        }

        node_p prev=node_x;
        node_p tmp=node_x->_next;
        while(tmp){
            if(tmp->_val<x){
                prev->_next=tmp->_next;
                tmp->_next=node_x;
                first->_next=tmp;
                first=first->_next;
                tmp=node_x->_next;
            }else{
                tmp=tmp->_next;
                prev=prev->_next;
            }
        }
        return head->_next;
    }

    //构造一个链表
    node_p create_list(int *array,int size)
    {
        assert(array);

        node dummy(-1);
        node_p prev=&dummy;
        node_p head=prev;
        for(int i=0;i<size;++i){
            node_p Node=new node (array[i]);
            prev->_next=Node;
            prev=prev->_next;
        }
        return head->_next;
    }
};

partition_list.cpp

#include "partition_list.h"

using namespace std;

int main()
{
    int array[]={1,4,3,2,5,2};
    Solution s1; 
    node_p list=s1.create_list(array,sizeof(array)/sizeof(array[0]));
    node_p newlist=s1.partition(list,4);
    
    node_p tmp=newlist;
    while(tmp){
        cout<<tmp->_val<<"  ";
        free(tmp);
        tmp=tmp->_next;
    }   
    cout<<endl;

    return 0;
}

运行结果:

Partition List


下面为leetcode实现的代码:

Partition List



《完》

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI