C++链表遍历和修改

Question

链表：

pointer2 -> [a]
pointer ->[a] -> [b] -> [c] -> [d] -> null    
pointer = b; //makes it point one down so it will be pointer -> [b] ->[c] -> [d] -> null    
pointer = pointer 2; //makes pointer point back to where it was pointing to before, both pointers point to [a]   
pointer2 = pointer->next; //makes pointer 2 point to [b]
pointer2->next = pointer->next; //makes [c] point to [b]

我的理解正确吗？节点可以指向自身吗？例如pointer->next = pointer->next？

基本上：

- pointer = pointer2 - 使指针指向pointer2所指向的内容？ - pointer->next = pointer2 - 使指针所指向的链节点指向pointer2所指向的链节点 - pointer->next = pointer2->next - 使指针所指向的链节点指向pointer2所指向链节点的下一个节点 - pointer = pointer2->next - 使指针指向pointer2所指向链节点的下一个节点。

是这样吗？

- Duxa

---

在普通的个人电脑上，指针变量只是一个整数，其值是内存中的地址。您可以像任何其他变量一样随意分配此值。当然，只要变量的类型兼容。 - Some programmer dude

是的，我理解指针是什么。我正在尝试确认我对于如何遍历链表的理解是否正确。就像底部的那些赋值语句是否做了我认为它们所做的事情。 - Duxa

Answer 1

节点可以指向它们自己吗？

正如其他人所说，这是完全可能的。但也许你真正想知道的是“是否有效？”答案取决于操作链表的代码。如果你正在编写该代码，那么 它是否有效取决于你。

例如，你可以决定当一个节点指向它自己时，表示链表的末尾。然后，下面是如何编写搜索整数链表中数字 3 的函数的示例：

struct ListNode {
    int value;
    ListNode* next;
};

bool containsThree(ListNode* list) {
    for (; list->next != list; list = list->next) {
        if (list->value == 3) {
            return true;
        }
    }
    // Also check final node
    if (list->value == 3) {
        return true;
    }
    return false;
}

或者你可以决定next == nullptr表示列表的末尾。在这种情况下，containsThree看起来会更像这样:

bool containsThree(ListNode* list) {
    for (ListNode* node = list; node; node = node->next) {
        if (node->value == 3) {
            return true;
        }
    }
    return false;
}

有了这个新函数，如果任何节点指向自身，则该函数将无限循环。您可以修复此问题，甚至检查列表中更大的循环，就像这样：

bool containsThree(ListNode* list) {
    std::set<ListNode*> seenNodes;
    for (ListNode* node = list; node; node = node->next) {
        if (seenNodes.count(node)) {
            break;
        }
        seenNodes.insert(node);
        if (node->value == 3) {
            return true;
        }
    }
    return false;
}

这个最终函数存在一个问题：与之前的函数相比，它的性能惩罚很大。因此，你需要决定是否允许列表中出现循环以及是否要在函数中检查它们，或者不允许循环。这两种方法都是正确的，你只需要做出决策并坚持执行即可。

（编辑：第一个示例函数有些混乱，因为结束循环的条件刚好在我们查找最后一个节点中的3之前。同时，无法传入空列表。这些问题都在nullptr示例中得到了解决，但实际上，即使使用“node == node->next”表示列表末尾的规则也可以解决它们。关键是在链表的末尾添加一个虚拟节点，并要求这个额外的节点具有这个属性。你不需要检查这个节点是否为3，而这个节点本身就代表了一个空列表。）

- Arthur Tacca

Answer 2

链接数据结构有一个指针用于当前数据，一个指向下一个数据（即指向下一个数据的当前数据的指针），如果是双向链表，则还有一个指向前一个数据的指针（即指向前一个数据的当前数据的指针）。

节点可以指向自己吗？例如 pointer->next = pointer->next ?

可以。这与将任何指针分配给它本身相同。但并不是非常有用。

• pointer->next = pointer2->next - 使指针所指向的链接节点指向指针2所指向的链接节点之后的一个节点
• pointer = pointer2->next - 使指针指向指针2所指向的链接节点之后的一个链接节点。

然而，在此之后，当前数据指针和下一个数据指针是相同的，并且指向相同的内容。这意味着，如果有人想要沿着这个链接列表遍历，如果没有指针检查，他们可能会陷入无限循环中。

- Griffin

Answer 3

除了最后一个指针分配，你是正确的：

...
pointer2 = pointer->next; //makes pointer 2 point to [b]: Ok
pointer2->next = pointer->next; //makes [c] point to [b]: Wrong

pointer2指向[b]，而pointer->next指向b。 最后一个指针赋值使得b指向了自身，导致：

pointer2 -> b -> b !

并且：

pointer -> a -> b -> b

你的误解可能来自于你的伪代码没有明确说明a、b、c和d是什么，next代表什么以及你在哪里使用地址。用C++写出所有这些内容，会更加清晰明了。

- Serge Ballesta