链表错误的中间

Question

我写了一个函数来打印单向链表的中间，但是当列表长度为奇数时，它不会打印它(不打印任何只是空格的东西(，当列表长度是偶数时，它打印的是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

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

• 进入mid_list()后，head是value=1节点，temp1和temp2设置为head。 请注意，您没有检查head的NULL，因此如果列表为空，您的代码将失败，但此示例中并非如此。

• 在第一次循环迭代中，temp1->next不是NULL，因此temp1设置为temp1->next->next哪个是value=3节点，temp2设置为temp2->next哪个是value=2节点。

• 在第二次循环迭代中，temp1->next是NULL的，因此循环中断，value=2节点被打印出来(不是你声称的空白(。目前为止，一切都好。

现场演示

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

• 进入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节点。

• 在第三次循环迭代中，temp1NULL因此访问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;
}

现场演示

或：

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

现场演示

根据您在迭代偶数大小列表时实际感兴趣的"中间"节点 - 中点左侧或右侧的节点。

Answer 2

你的代码中有一个错误，在 while 条件下，你必须检查"temp1->next"，因为你在循环中指向它的下一个，如果 temp->next 是 NULL，那么 temp1->next->next 将是未定义的。下面的代码可以正常工作：

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

Answer 3

如果我理解正确，您正在寻找中间节点。下一个片段可以解决问题：

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 开始(。