86分割链表表_大小分隔

86.大小分隔

下面是题目

下面是题目给出的模板

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
 
    }
};

我利用了两个队列，实现了这个操作

/**
	因为这个题目再去想怎么直接在链表上断一断，拼一拼已经是非常困难的了，所以我考虑新建队列
	而且我们又要保持原来的节点的相对位置相同，所以我们要保证一个先进先出的数据结构--队列
	
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        queue<int>smaller;//用来记录小于x的数值
        queue<int>larger;//用来记录大于等于x的数值
        ListNode *cur = head;
        //首先让链表中的值全部入列
        while(cur)
        {
            cur->val>=x? larger.push(cur->val):smaller.push(cur->val);
            cur = cur ->next;
        } 
        //然后新建一个dummyNode
        ListNode *dummy = new ListNode(0);
       	head = dummy;//这里其实就是另起炉灶,让head不再指向原来的链表了
        while(!smaller.empty())
        {
            //首先，把所有smaller中的元素依次建立新结点，然后更新dummyNode，然后出列
            ListNode *newNode = new ListNode(smaller.front());
            dummy->next = newNode;
            dummy = dummy->next;
            smaller.pop();
        }
        while(!larger.empty())
        {	
            //对于larger队列，在smaller队列完成操作之后再继续，操作顺序和smaller队列相同
            ListNode *newNodela = new ListNode(larger.front());
            dummy->next = newNodela;
            dummy = dummy->next;
            larger.pop();
        }
        //最后返回head->next,因为head = dummy
        return head->next;
       
    }
};

还有一个解法我认为更加美观

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        //直接新建两个链表，一个存储小于x的，一个存储大于等于x的，然后让他们两个相连！
        ListNode na(0),nb(0);
        ListNode *a=&na,*b=&nb;
        while(head!=nullptr){
            int v=head->val;
            if(v<x) a->next=head,a=head;
            else b->next=head,b=head;
            head=head->next;
        }
        a->next=nb.next;
        b->next=nullptr;
        return na.next;
    }
};