將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分爲兩部分

回答

相關問題