Result passing problem in C++


  • 1
    L

    I find it runs well inside the function. But when it jumps out, the pointer *head doesn't change. I know the problem here is that C++ only copy the value of pointer into the function, not the pointer itself. But how can I fix this problem ?
    Here is my code:

    class Solution {
    public:
        void reorderList(ListNode *head) {
            if(head == NULL){
                return;
            }
            
            deque<ListNode> myDeque;
            
            ListNode *ptr = head;
            while(ptr != NULL){
                myDeque.push_back(*ptr);
                ptr = ptr->next;
            }
            
            int flag = 0;
            head = &myDeque.front();
            myDeque.pop_front();
            ptr = head;
            
            while(!myDeque.empty()){
                if(flag == 0){
                    flag = 1;
                    ptr->next = &myDeque.back();
                    myDeque.pop_back();
                }
                else{
                    flag = 0;
                    ptr->next = &myDeque.front();
                    myDeque.pop_front();
                }
                ptr = ptr->next;
            }
            ptr->next = NULL;
        }
    };

  • 0
    S

    Since the first node of the reordered list L0 is the same one as the first node of the original list, you SHOULD NOT change 'head' or attempt to pass it back. If you find you need to pass a modified 'head' to the caller of this function, it means your code is probably NOT in-place, and thus does not satisfy the requirement of this problem.

    A quick fix could be to use deque<ListNode*> instead of deque <ListNode>, avoiding copying the listnodes around. Of course, the deque is not necessary. You can reverse the second half of the list, and scan to the middle from both ends. That way you can solve this problem with O(1) memory.


  • 0
    Z

    why can use other datastructure


Log in to reply
 

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