How to make my c++ code's efficient and simple?


  • 0
    S
    ListNode* partition(ListNode* head, int x) {
    		if (head == NULL || head->next == NULL)
    			return head;
    		auto newhead = new ListNode(0), post = head, prepost = newhead;
    		newhead->next = head;
    
    		while (post != NULL && post->val < x){
    			post = post->next;
    			prepost = prepost->next;
    		}
    		auto pre = prepost;
    
    		while (post != NULL){
    			auto p = post;
    			post = post->next;
    			if (p->val < x){
    				prepost->next = p->next;
    				p->next = pre->next;
    				pre->next = p;
    				//update ptr
    				pre = pre->next;
    			}
    			else
    				prepost = p;
    		}
    
    		return newhead->next;
    	}

  • 0
    Y
    class Solution {
    public:
    void Append(ListNode *&tail, int x) {
      tail->next = new ListNode(x);
      tail = tail->next;
    }
    
    ListNode* partition(ListNode* head, int x) {
      ListNode *A = new ListNode(0), *B = new ListNode(0);
      ListNode *tailA = A, *tailB = B;
      while (head != NULL) {
        if (head->val < x) Append(tailA, head->val);
        else Append(tailB, head->val);
        head = head->next;
      }
      tailA->next = B->next;
      return A->next;
    }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.