LeetCode 86.Partion List

LeetCode 86.Partion 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より大きい元素の前にあります.私のもとの考えはcです.最初から最後までチェーンを通して、preとcurのポインタを設定して、それぞれ現在の結点と現在の結点の前の結点を指します.xの要素に出会ったら、headの前に挿入して、この元素を削除します.

 while(cur){
            if(cur->val<x){
                pre->next=cur->next;
                ListNode* tmp=new ListNode(0);
                tmp->val=cur->val;
                tmp->next=newhead->next;
                newhead->next=tmp;
                newhead=tmp;
                cur=cur->next;
            }
            else{
                pre=pre->next;
                cur=cur->next;
            }

後に提出する時、いくつかのテストデータがあって、私はやっと私のこの考えに問題があることを発見しました.例えば(1、2、3)、x=3、このようにして(2、1、3)に戻ります.明らかに間違っています.実は私が以前考えていたのはxの前にxより小さい元素がない場合です.だからxの前の要素を加えてxより小さい場合(この時pre、curはそのまま後に移動すればいいです.).

while(cur&&cur->val<x){
            if(cur->next==NULL)
             break;//        
            pre=pre->next;
            cur=cur->next;
            newhead=newhead->next;
        }

コードの実装

/**
 * 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) {
        if(head==NULL || head->next==NULL)
          return head;

        ListNode* result=new ListNode(0);
        result->next=head;
        ListNode* newhead=result;
        ListNode* pre=result;
        ListNode* cur=head;
        while(cur&&cur->valif(cur->next==NULL)
             break;
            pre=pre->next;
            cur=cur->next;
            newhead=newhead->next;
        }
        while(cur){
            if(cur->valnext=cur->next;
                ListNode* tmp=new ListNode(0);
                tmp->val=cur->val;
                tmp->next=newhead->next;
                newhead->next=tmp;
                newhead=tmp;
                cur=cur->next;
            }
            else{
                pre=pre->next;
                cur=cur->next;
            }
        }
        return result->next;
    }
};

ps:私が見たもう一つの簡潔な考え方は、二つのチェーンを設置して、それぞれxより小さい元素とxより大きい(または等しい)元素を記憶し、最後に二つのチェーンの頭と尾を連結すればいいです.

        ListNode p = new ListNode(0);
        ListNode pHead = p;
        ListNode q = new ListNode(0);
        ListNode qHead = q;
        //  
        while(head != null){
            if(head.val < x){
    //next = head;
                p = p.next;
            }else{
    //>=x   
                q.next = head;
                q = q.next;
            }
            head = head.next;
        }
        p.next = qHead.next;
        q.next = null;//       
        return pHead.next;