0

给定一个列表，将其分成两个子列表——一个用于前半部分，一个用于后半部分。如果元素的数量是奇数，则额外的元素应该放在前面的列表中。所以FrontBackSplit()在列表上{2, 3, 5, 7, 11}应该产生两个列表{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;
}

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

4

2 回答 2

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。这正是这个函数想要的行为，不是吗？

于 2013-07-22T11:11:06.040 回答
0

还有另一种方法；

使用循环计算链表中有多少元素。

如果它的一对 - 第一个列表在头（第一个元素的地址）到 i=n/2 元素之间。第二个列表在 i=0.5n+1 个元素到最后一个元素之间。

否则，第一个列表在头到 i=0.5n+1 元素之间，第二个在 i=0.5n+2 到最后一个之间。

为方便起见，当您运行循环计算元素数量时，使用一个变量来保留最后一个和中间一个的位置，以便在需要时使用它们。

于 2013-07-22T12:25:16.360 回答