c - 将链表分成两部分

Question

给定一个列表，将其分成两个子列表——一个用于前半部分，一个用于后半部分。如果元素的数量是奇数，多余的元素应该放在前面的列表中。所以列表 {2, 3, 5, 7, 11} 上的 FrontBackSplit() 应该产生两个列表 {2, 3, 5} 和 {7, 11}。

代码是这样的

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

问题是我没有获得最佳运行时间和有时预期的输出。

Answer 1

通常，您的代码适用于偶数大小的列表。考虑一个包含 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。这正是该函数想要的行为，不是吗？