指针指针：分区链接列表

Question

我试图变得更容易与指针。所以，为了好玩，我采取了以下C++函数，围绕分隔值

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; 
} 

一个链表，我试图改变它采取C风格的双指针来代替。我做了一个无意识的发现替换，这没有奏效。寻找到它，我发现我的问题的根源，但我还是真的不明白这是怎么回事...

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); 
} 

在第一循环中，调试打印线的所有四个附近的顶部函数的while循环打印“1”。但是，在第二个循环中，它们打印“2”，“2”，“2”，“3”？

任何人都可以解释发生了什么？什么是使用双指针而不是对指针的引用的正确方法？

谢谢！

Answer 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？