0

为什么我的 C 代码运行无限循环，如何修复它以获得预期的输出？

我应该将节点从 A 反转到 B

所以假设我输入：

2 5

1 2 3 4 5 6 7

第一行是指示我应该从哪个索引到哪个索引来反转节点所以这里3是节点A，6是节点B。第二行是我给出的列表。所以，我期待输出：1 2 6 5 4 3 7

这是我的代码：

ListNode *reverseSegment(ListNode *head, int start, int end)
{
  // Write your code here

  // Condition to Check if B is valid (if B is valid, then A is valid)
  ListNode *temp1 = head;
  int count = 0;
  while (temp1 != NULL)
  {
    temp1 = temp1->next;
    count++;
  }

  // Condtion to check if index out of range or invalid
  if (count < end)
  {
    return head;
  }

  // Declaring Pointers
  ListNode *prev = NULL, *cur = head, *next = NULL, *endptr = NULL;
  ListNode *temp2 = head; 
  int diff = end - start;

  // Point endptr to the last node of the list
  while (temp2->next != NULL)
  {
    endptr = temp2; 
  }
  // Point next ptr to the node after A
  // Point prev pointer to the node after B
  //next = cur->next;
  prev = endptr;
  
  // Reversing the node from B to A
  while ((diff+1) > 0 )
  {
    next = cur->next;
    cur->next = prev;
    prev = cur;
    cur = next;
    diff--;
  }
  // Point head ptr to node B
  head->next = prev;

  //return head;
}
4

2 回答 2

0

这个 while 循环将是无限的，因为temp2在每个循环中都不会修改：

  // Point endptr to the last node of the list
  while (temp2->next != NULL)
  {
    endptr = temp2; 
  }

看起来您确实需要在 A 和 B 之前搜索节点，所以这样的事情可能是更简单的解决方案（对于start > 0）：

  int      count = 0;
  ListNode *cur = head;

  ListNode *start_node_prev;
  ListNode *start_node;
  ListNode *start_node_next;
  ListNode *end_node_prev;
  ListNode *end_node;
  ListNode *end_node_next;

  while(count < start)
  {
     start_node_prev = cur;
     cur             = cur->next;
     start_node      = cur;
     start_node_next = cur->next;
  }

  while(count < end)
  {
     end_node_prev = cur;
     cur           = cur->next;
     end_node      = cur;
     end_node_next = cur->next;
  }

  start_node->next = end_node_next;
  end_node->next   = start_node_next;

  start_node_prev->next = end_node;
  end_node_prev->next   = start_node;

请注意，如果start == 0.

此外，应包括检查start < end.

于 2022-02-02T15:44:45.940 回答
0

你做的事情有点太复杂了，尤其是你迭代的太多了。

一开始你可能想检查一下，如果start确实比end也小！顺便说一句：负索引毫无意义，所以我建议使用无符号类型来指定它们，例如size_t.

您现在对和之间的偏移量感兴趣，所以我先计算一下：startend

end -= start;

您将不再需要原始值，请参见下文。

然后你从头开始迭代head：

if(!head || start == end) // empty list or sequence
{
    return head;
}

ListNode* startNode = head;
for(;start; --start)
{
    if(!startNode->next)
    {
       // no nodes left -> start is not valid!
       return head;
    }
    startNode = startNode->next;
}
ListNode* endNode = startNode;
for(;end; --end)
{
    if(!endNode->next)
    {
       // no nodes left -> end is not valid!
       return head;
    }
    endNode = endNode->next;
}

现在两者start和end都被减为 0，但无论如何你不再需要它们了——你找到了开始和结束节点，从现在开始你可以直接对节点进行操作。

在列表段中，您现在可以通过简单地交换每个节点的prev和next指针来反转：

for(ListNode* cur = endNode; cur != startNode;  cur = cur->next)
// note that you swapped pointers already when
// getting here so you still iterate backwards: ^^^^^^^^^^^^^^^
{
    ListNode* tmp = cur->next;
    cur->next = cur->prev;
    cur->prev = tmp;
}

现在要修复:endNode的前任指向什么是它的后继，然而，它需要得到起始节点的后继，而起始节点还没有改变。所以我们需要：

ListNode* tmp = endNode->prev;
endNode->prev = startNode->prev;   // tail now fixed completely
startNode->prev = startNode->next; // swap direction
startNode->next = tmp;             // set to the remaining list

最后：

return endNode->prev ? head : endNode;

如果startNode有前任，那么我们从中间的某个地方开始反转，因此需要返回head- 否则我们从列表的开头反转并且原来的头节点已经被移开，而原来的结束节点现在是新的头。

请注意，上面是未经测试的代码 - 如果您发现错误，请自行修复...

于 2022-02-02T16:08:06.473 回答