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 - 使指针指向指针 2 指向的任何位置？
pointer->next = pointer2 - 使指针指向的link节点指向pointer2link节点
pointer->next = pointer2->next - 使pointer指向的link节点指向pointer2指向的link节点之后的一个节点
pointer = pointer2->next - 使指针指向 link 节点，在第一个 pointer2 指向之后。

对吗？

Answer 1

你是对的，除了最后一个指针赋值：

...
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++写的，会更清楚

Answer 2

Linked data structure 有一个指向当前数据的指针，一个指向下一个数据（这是指向下一个当前数据的指针），如果是双向链表，则一个指向前一个数据（这是指向前一个的当前数据的指针）。

Can nodes point to themselves? like pointer->next = pointer->next ?

是的。这与将任何指针分配给自身相同。不是很有用。

pointer->next = pointer2->next - make link node that pointer points to point to one after link node that pointer2 points to

pointer = pointer2->next - make pointer point to the link node one after the one pointer2 points to.

但是在这之后，当前数据指针和下一个数据指针是相同的并且指向相同的东西。这意味着如果有人想遍历这个链表，如果他们没有指针检查，他们可能会陷入无限循环。

Answer 3

Can nodes point to themselves?

正如其他人所说，这当然是可能的。但也许您的意思是 "is it valid?"。答案是，它取决于操作链表的代码。如果您正在编写该代码，那么它是否有效取决于您。

例如，您可能会决定当一个节点指向自身时，则表示链表的末尾。然后，您可以编写一个函数来搜索整数链表中的数字 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意味着列表结束”规则也可以修复它们。关键就是在链表的末尾增加一个dummy节点，并且要求这个多出的节点有这个属性。不需要检查这个节点的三性，这样的节点本身就代表一个空列表。）

C++链表遍历和修改

C++ Linked List traversal and modification

c++

pointers

linked-list

singly-linked-list