給定單鏈表的交替分割

Question

編寫一個函數AlternatingSplit（），該函數接受一個列表並將其節點分成兩個較小的列表'a'和'b'。子列表應該由原始列表中的交替元素組成。所以如果原始列表是0-> 1-> 0-> 1-> 0-> 1，那麼一個子列表應該是0-> 0-> 0，另一個應該是1-> 1-> 1。

有關該問題的更多細節 - http://www.geeksforgeeks.org/alternating-split-of-a-given-singly-linked-list/

現在，我做了這個代碼，它的成功運行

#include<stdio.h> 
#include<stdlib.h> 
struct node 
{ 
    int num; 
    node *next; 
}; 

node *start1 = NULL, *start2 = NULL, *start3 = NULL; 

void push() 
{ 
    node *temp = (node *)malloc(sizeof(node)); 
    printf("Enter number = "); 
    scanf("%d", &temp->num); 
    temp -> next = start1; 
    start1 = temp; 
} 

void split() 
{ 
    while(start1 != NULL) 
    { 
     node *temp1 = (node *)malloc(sizeof(node)); 
     temp1 ->num = start1 ->num; 
     temp1->next = start2; 
     start2 = temp1; 
     start1 = start1 -> next; 

     if(start1 != NULL) 
     { 
      node *temp2 = (node *)malloc(sizeof(node)); 
      temp2 ->num = start1 ->num; 
      temp2->next = start3; 
      start3 = temp2; 
      start1 = start1 -> next; 
     } 
    } 
} 

int main() 
{ 
    int n; 
    scanf("%d", &n); 

    while(n--) 
     push(); 

    split(); 

    node *temp = start2; 

    while(temp != NULL) 
    { 
     printf("%d ", temp ->num); 
     temp = temp ->next; 
    } 

    printf("\n"); 
    temp = start3; 

    while(temp != NULL) 
    { 
     printf("%d ", temp ->num); 
     temp = temp ->next; 
    } 

    return 0; 
} 

和設置有問題的代碼是 -

/*Program to alternatively split a linked list into two halves */ 
#include<stdio.h> 
#include<stdlib.h> 
#include<assert.h> 

/* Link list node */ 
struct node 
{ 
    int data; 
    struct node* next; 
}; 

/* pull off the front node of the source and put it in dest */ 
void MoveNode(struct node** destRef, struct node** sourceRef) ; 

/* Given the source list, split its nodes into two shorter lists. 
If we number the elements 0, 1, 2, ... then all the even elements 
should go in the first list, and all the odd elements in the second. 
The elements in the new lists may be in any order. */ 

void AlternatingSplit(struct node* source, struct node** aRef, struct node** bRef) 
{ 
    /* split the nodes of source to these 'a' and 'b' lists */ 
    struct node* a = NULL; 
    struct node* b = NULL; 

    struct node* current = source; 

    while (current != NULL) 
    { 
     MoveNode(&a, &current); /* Move a node to list 'a' */ 

     if (current != NULL) 
     { 
      MoveNode(&b, &current); /* Move a node to list 'b' */ 
     } 
    } 

    *aRef = a; 
    *bRef = b; 

} 

/* Take the node from the front of the source, and move it to the front of the dest. 
It is an error to call this with the source list empty. 

Before calling MoveNode(): 
source == {1, 2, 3} 
dest == {1, 2, 3} 

Affter calling MoveNode(): 
source == {2, 3}  
dest == {1, 1, 2, 3}  
*/ 

void MoveNode(struct node** destRef, struct node** sourceRef) 
{ 
    /* the front source node */ 
    struct node* newNode = *sourceRef; 
    assert(newNode != NULL); 

    /* Advance the source pointer */ 
    *sourceRef = newNode->next; 

    /* Link the old dest off the new node */ 
    newNode->next = *destRef; 

    /* Move dest to point to the new node */ 
    *destRef = newNode; 
} 

/* UTILITY FUNCTIONS */ 
/* Function to insert a node at the beginging of the linked list */ 

void push(struct node** head_ref, int new_data) 
{ 
    /* allocate node */ 
    struct node* new_node = (struct node*) malloc(sizeof(struct node)); 

    /* put in the data */ 
    new_node->data = new_data; 

    /* link the old list off the new node */ 
    new_node->next = (*head_ref);  

    /* move the head to point to the new node */ 
    (*head_ref) = new_node; 
} 

/* Function to print nodes in a given linked list */ 

void printList(struct node *node) 
{ 
    while(node!=NULL) 
    { 
     printf("%d ", node->data); 
     node = node->next; 
    } 
} 

/* Drier program to test above functions*/ 
int main() 
{ 
    /* Start with the empty list */ 
    struct node* head = NULL; 
    struct node* a = NULL; 
    struct node* b = NULL; 

    /* Let us create a sorted linked list to test the functions 
    Created linked list will be 0->1->2->3->4->5 */ 
    push(&head, 5); 
    push(&head, 4); 
    push(&head, 3); 
    push(&head, 2); 
    push(&head, 1);          
    push(&head, 0); 

    printf("\n Original linked List: "); 
    printList(head); 

    /* Remove duplicates from linked list */ 
    AlternatingSplit(head, &a, &b); 

    printf("\n Resultant Linked List 'a' "); 
    printList(a);    

    printf("\n Resultant Linked List 'b' "); 
    printList(b);    

    getchar(); 

    return 0; 

} 

我在這裏查詢考慮到時間複雜性，空間複雜性和其他因素，這兩個代碼中的哪一個對於這個問題更高效和更正確？ 爲什麼？ 詳細的解釋會更有幫助。

Answer 1

當你只是分割一個鏈表時，你不需要任何內存分配，只需要在指針周圍洗刷就足夠了。

您的代碼在分割時會執行內存分配，所以它的效率相當低，模型答案代碼要好得多。

但更糟的是，你的代碼泄漏內存。它失去了指向原始列表元素的指針而沒有釋放它們。所以你的代碼實際上是一個錯誤的方式。

---

要解決只是內存泄漏，這確實是個bug，你需要兩個start1 = start1 -> next;線改成這樣：

node *tmp_next = start1->next; 
free(start1); 
start1 = tmp_next; 

對於其他的變化，標準答案是一個很好的例子，但最重要的事情是：擺脫額外的malloc調用，並通過移動節點進行拆分，而不是分配新節點和複製數據（並且在上述bug修復之後釋放舊節點）。然後擺脫全局變量，而不是像模型答案中那樣向函數添加參數。

Answer 2

又一個快速分裂，沒有新的分配，並保持原來的列表縮小到奇數元素，而形成新的名單，甚至那些與評論一起上的每個關鍵步驟

void split_in_evenodd(node *orig) 
{ 
    if(!orig) 
     return; 

    node *e, *cur, *e_hd; 

    e = orig->next; // point first even member 
    e_hd = e; // keep a head pointer to even list 

    if(!e) // covers the case of list with single element 
     return; 

    orig->next = e->next; // make orig skip the even node 
    cur = orig->next; // cur moves to next odd node 

    while(cur && cur->next) { 
     e->next = cur->next; // even pointing to next even node 
     e = e->next; // move even list forward 

     cur->next = e->next; // update odds next 
     cur = e->next;// move current forward (to next odd) 
    } 
}