随机链表的复制数据结构oj题（CM11）

目录

问题描述

题目解读

解决代码

问题描述

题目解读

这里给了一个头结点pHead，和一个定值x，这里要的是比x值小的结点要在x这个结点的左边，并且这里写着不改变数据顺序，也就是相对顺序。比如：{5，2，1，3，6},x=3;最终返回的顺序为{2，1，3，5，6}。

这里我们可以想到这里是用到单链表，很难从后往前去交换，所以我们这里就可以设置两个头结点，其中一个链表用来保存小于x的结点，还有一个保存大于等于x的结点，最后就能将两个链表合并在一起。

解决代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
    ListNode* partition(ListNode* pHead, int x) {
        ListNode* lessHead,*lessTail;
        lessHead = lessTail =(ListNode*)malloc(sizeof(ListNode));
        if(lessHead == NULL)
        {
            perror("malloc fali1");
            exit(1);
        }
        ListNode* greaterHead,*greaterTail;
        greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));
        if(greaterHead == NULL)
        {
            perror("malloc fali2");
            exit(1);
        }
        //寻找
        ListNode* pcur = pHead;
        while(pcur)
        {
            //小
            if(pcur->val < x)
            {
                lessTail->next = pcur;
                lessTail = lessTail->next;
            }
            //大
            else {
            greaterTail->next = pcur;
            greaterTail = greaterTail->next;
            }
            pcur = pcur->next;
        }
        //合并
        lessTail->next=greaterHead->next;
        greaterTail->next = NULL;//防止过度访问
        ListNode* ret = lessHead->next;    
        //销毁  
        free(lessHead);
        free(greaterHead);
        return ret;
    }
};