[LeetCode] Partition List

Partition List 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 .
問題解決の考え方:
この問題の意味は、チェーンテーブルと値xを指定し、チェーンテーブルのx未満のノードをx以上のノードの前に置くが、チェーンテーブルの安定性を維持することである.この問題は比較的簡単で、チェーンテーブルをスキャンして、xより小さいものをチェーンテーブルにして、残りのノードをチェーンテーブルにして、それから2つのチェーンテーブルを接続すればいいです.

/**
 * 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) {
        ListNode* myHead1 = new ListNode(0);    //      
        ListNode* myHead2 = new ListNode(0);    //      
        ListNode* tail1 = myHead1;
        ListNode* tail2 = myHead2;
        ListNode* p = head;
        while(p!=NULL){
            if(p->val<x){
                tail1->next = p;
                tail1 = tail1->next;
            }else{
                tail2->next = p;
                tail2 = tail2->next;
            }
            p = p->next;
        }
        tail1->next = myHead2->next;
        tail2->next = NULL;
        p = myHead1->next;
        delete myHead1;
        delete myHead2;
        return p;
    }
};