Algorithme leetcode 86. Liste des liens séparés

Liens vers les sujets：86. Liste de liens séparés

Ideas

Algorithmes：Simulation
Structure des données：Liste des liens
Idées：（J'ai d'abord essayé d'échanger des pointeurs en place,Il a réussi à s'évanouir et à ouvrir la solution.）
D'abord, créez deux noeuds virtuels,Utilisé séparément pour maintenir les exigences inférieures àxEt plus dexNode of,Puis traversez la liste,Un noeud est rencontré pour déterminer quel type,Ensuite, mettez - le derrière le noeud virtuel correspondant.

Code

C++

class Solution {
    
public:
    ListNode* partition(ListNode* head, int x) {
    
        ListNode *small = new ListNode(0), *large = new ListNode(0);
        ListNode *smallHead = small, *largeHead = large;
        while (head != nullptr) {
    
            if (head->val < x) {
    
                small->next = head;
                small = small->next;
            } else {
    
                large->next = head;
                large = large->next;
            }
            head = head->next;
        }
        large->next = nullptr;
        small->next = largeHead->next;
        return smallHead->next;
    }
};