将Linklist分为两部分

给出一个列表，将其分成两个子列表 - 一个用于前半部分，另一个用于后半部分。如果元素的数量是奇数，额外的元素应该放在前面的列表中。因此，名单{2, 3, 5, 7, 11}上的FrontBackSplit()应该产生两个列表{2, 3, 5}和{7, 11}。将Linklist分为两部分

代码是这样的。

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

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

来源

2013-07-22 someone

你有清单准备好了吗？如果是的话，除以2，由许多节点推进并分割。 – Vesper

有什么问题？当你调用函数时会发生什么？ – nouney

如何确定“不是最佳运行时”，输出有什么问题？ –

通常，您的代码适用于大小均匀的列表。考虑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-22 11:11:06

还有另一种方法;

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

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

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

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

来源

2013-07-22 12:25:16 user2600366

错误的答案... – someone

将Linklist分为两部分

回答

相关问题