c - 将链接列表分为两部分

给定一个列表，将其分成两个子列表-一个用于前半部分，一个用于后半部分。如果元素的数目是奇数，那么额外的元素应该放在前面的列表中因此，列表中的FrontBackSplit()应该产生两个列表{2, 3, 5, 7, 11}和{2, 3, 5}。
代码就是这个。

void FrontBackSplit(Node *head, Node **front, Node **back) {
  if (!head) return;  // Handle empty list
  Node *front_last_node;
  Node *slow = head;
  Node *fast = head;
  while (fast) {
    front_last_node = slow;
    slow = slow->next;
    fast = (fast->next) ? fast->next->next : NULL;
  }
  front_last_node->next = NULL;  // ends the front sublist
  *front = head;
  *back = slow;
}

问题是我没有得到最好的运行时，有时预期的产出。

最佳答案

一般来说，您的代码对于大小均匀的列表很好。考虑一个由4个元素a->b->c->d->null组成的列表，并查看算法跟踪。

A    slow, fast, head
B
C
D
NULL

A    front_last_node, head
B    slow
C    fast
D
NULL

A    head
B    front_last_node
C    slow
D
NULL fast

然后删除链接b->c并返回两个列表：a->b和c->d。这正是这个函数想要的行为，不是吗？

关于c - 将链接列表分为两部分，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/17782291/