1

I'm trying to become more facile with pointers. So, for fun, I took the following C++ function that partitions a linked list around a value

void partitionList(lnode<int> *& head, int val) {
    lnode<int> * front = nullptr;
    lnode<int> * back = nullptr;
    lnode<int> * curr = head;

    while (curr) {
        lnode<int> * next = curr->next;
        if (curr->data < val) {
            curr->next = front;
            front = curr;
        } else {
            curr->next = back;
            back = curr;
        }
        curr = next;
    }

    curr = front;
    while (curr->next) {
        curr = curr->next;
    }
    curr->next = back;
    head = front;
}

and I tried to change it to take a C-style double pointer instead. I did a mindless find-replace, which didn't work. Looking into it, I found the source of my problem, but I still don't really understand what's going on...

void partitionList(lnode<int> ** head, int val) {
    lnode<int> * front = nullptr;
    lnode<int> * back = nullptr;
    lnode<int> ** curr = head;

    while (*curr) {
        lnode<int> * entry = *curr;

        std::cout << (*curr)->data << std::endl; // On second loop, prints 2
        std::cout << entry->data << std::endl; // On second loop, prints 2

        lnode<int> * next = entry->next; // This assignment does something

        std::cout << entry->data << std::endl; // On second loop, prints 2
        std::cout << (*curr)->data << std::endl; // On second loop, prints 3!

        if ((*curr)->data < val) {
            (*curr)->next = front;
            front = *curr;
        } else {
            (*curr)->next = back;
            back = *curr;
        }
        curr = &next;
    }

    *curr = front;
    while ((*curr)->next) {
        (*curr) = (*curr)->next;
    }
    (*curr)->next = back;
    head = &front;
}

int main() {
    lnode<int> * tail = new lnode<int>(8, nullptr);
    lnode<int> * seven = new lnode<int>(7, tail);
    lnode<int> * six = new lnode<int>(6, seven);
    lnode<int> * five = new lnode<int>(5, six);
    lnode<int> * four = new lnode<int>(4, five);
    lnode<int> * three = new lnode<int>(3, four);
    lnode<int> * two = new lnode<int>(2, three);
    lnode<int> * head = new lnode<int>(1, two);

    partitionList(&head, 6);
}

On the first loop, all four of the debug print lines near the top of the function's while loop print "1". However, on the second loop, they print "2", "2", "2", "3"?

Can anyone explain what's going on? What's the right way to use a double pointer instead of a reference to a pointer?

Thanks!

4

1 回答 1

1 
void partitionList(lnode<int> *& head, int val) {
    ...
    head = front; // <= head is modified
}

但这里不是

void partitionList(lnode<int> ** head, int val) {
    ...
    head = &front; // try it with *head = front
}

如果你想快速更换这个

void partitionList(lnode<int> *& head, int val) {
   ...
   lnode<int> * curr = head;

写这个：

void partitionList(lnode<int> ** head, int val) {
    ...
    lnode<int> * curr = *head;

你为什么修改*cur为**cur？

于 2013-05-13T21:43:14.393 回答