链表错误的中间

Question

我写了一个函数来打印单链表的中间部分，但是当列表长度为奇数时，它不打印它（不打印任何东西只是空白 space），当列表length是偶数，打印的是mid（节点之和，正确）。

我有以下代码：

struct Node {
    int value;
    Node* next;
};
 
Node* head = NULL;

void insert_element2(int x);
void mid_list(Node* head);

int main() {

    insert_element2(1);
    insert_element2(2);
    insert_element2(3); //etc 


    mid_list(head);

    return 0;
}


void insert_element2(int x) {
    Node* temp1 = new Node();
    temp1->value = x;
    temp1->next = NULL;

    if (head == NULL) 
        head = temp1;
    else {
        Node* temp2 = head;
        while(temp2->next != NULL) {
            temp2 = temp2->next;
        }
        temp2->next = temp1;
    }
}


void mid_list(Node* head) {
    Node* temp1 = head;
    Node* temp2 =  head;

    while (temp1->next != NULL) {  **// When i change "temp->next" with "temp" is acting opposite(even/odd)**
        temp1 = temp1->next->next;
        temp2 = temp2->next;
    }

    cout << temp2->value;
}

Answer 1

如果我没理解错的话，你是在找中间节点。下一个片段可以解决问题：

void mid_list(Node* head) 
{
    Node* temp1 = head;
    
    auto nodeCount = 0u;
    while (temp1->next != nullptr) // walk through nodes if exists
    {
        temp1 = temp1->next;
        ++nodeCount; //count valid nodes
    }

    temp1 = head; //reset the temp
    for (auto ii=0u; nodeCount / 2 > ii; ++ii ) // walk to the middle node from the head
    {
        temp1 = temp1->next;
    }
    if (nullptr != temp1) // sanity check
        std::cout << temp1->value;
}

对于奇数个条目，它是一个真正的中间节点，因为它要么是之前的节点（如果你从 0 开始计数），要么是“中间”索引之后的节点（如果从 1 开始）。

Answer 2

让我们逐步了解您的奇数列表示例的逻辑：

进入mid_list()后，head为value=1节点，temp1和temp2设置为head。请注意，您没有为 NULL 检查 head，因此如果列表为空，您的代码将失败，但在本示例中并非如此。
在第一次循环迭代中，temp1->next 不是 NULL，因此 temp1 设置为 temp1->next->next，即 value=3 节点，temp2 设置为 temp2->next，即 value=2 节点。
在第 2 次循环迭代中，temp1->next 是 NULL，因此循环中断，并打印 value=2 节点（不是空白 space，就像你声称的那样）。到目前为止，还不错。

Live Demo

现在，让我们逐步了解偶数列表的逻辑：

进入mid_list()后，head为value=1节点，temp1和temp2设置为head.
在第一次循环迭代中，temp1->next 不是 NULL，因此 temp1 设置为 temp1->next->next，即 value=3 节点，temp2 设置为 temp2->next，即 value=2 节点。
在第二次循环迭代中，temp1->next 不是 NULL，因此 temp1 设置为 temp1->next->next，即 NULL ，并且 temp2 被设置为 temp2->next 这是 value=3 节点。
在第 3 次循环迭代中，temp1 是 NULL，因此访问 temp1->next 是 未定义的行为 和代码失败。

因此，要解决此问题，您需要将循环更改为更像这样的内容：

void mid_list(Node* head)
{
    if (head == NULL) return;

    Node* temp1 = head;
    Node* temp2 = head;

    while (temp1->next != NULL) {
        temp1 = temp1->next->next;
        if (temp1 == NULL) break;
        temp2 = temp2->next;
    }

    cout << temp2->value;
}

Live Demo

或者：

void mid_list(Node* head)
{
    if (head == NULL) return;

    Node* temp1 = head;
    Node* temp2 = head;

    while ((temp1 != NULL) && (temp1->next != NULL)) {
        temp1 = temp1->next->next;
        temp2 = temp2->next;
    }

    cout << temp2->value;
}

Live Demo

取决于在迭代偶数大小的列表时您真正感兴趣的“中间”节点 - 中点左侧或右侧的节点。

Answer 3

您的代码中有一个错误，在 while 条件下，您必须检查“temp1->next”，因为您在循环中指向它的下一个，如果 temp->next 为 NULL，则 temp1->next- >接下来是 undefined.The 下面的代码可以正常工作：

    void mid_list(Node* head) {
    Node* temp1 = head;
    Node* temp2 =  head;

    while (temp1!=NULL && temp1->next != NULL) {  // here I have modified this line.
       temp1 = temp1->next->next;
       temp2 = temp2->next;
    }

    cout << temp2->value;
    }

链表错误的中间

Middle of a linked list bug

c++

singly-linked-list