拆分鏈表到一半

我試圖創建一個功能splitlist（），將單鏈表分成兩個子列表 - 一個是前半部分，一個是後半。我想出了下面這將是第一次，我調用該函數的工作代碼，但是當我反覆調用函數，程序崩潰。有關如何更改我的代碼以防止出現此類錯誤的任何建議？函數splitlist（）是無效的，因爲它打印兩個包含frontList和backList的列表。拆分鏈表到一半

typedef struct _listnode { 
int item; 
struct _listnode *next; 
} ListNode;   

typedef struct _linkedlist { 
int size; 
ListNode *head; 
} LinkedList; 

    void splitlist(LinkedList* list1, LinkedList * firsthalf, LinkedList *secondhalf)  
{ 
    ListNode *cur = list1->head; 
    ListNode *front = firsthalf->head; 
    ListNode *back = secondhalf->head; 
    int totalnodes = list1->size; 
    int i; 
    if (totalnodes % 2 != 0)     //if odd number of elements, add 1 to make it easier for traversal of list 
    { 
     totalnodes = totalnodes + 1; 
    } 
    int halfnodes = totalnodes/2; 


    { 
     for (i = 0; i < halfnodes; i++)    
     { 
      if (firsthalf->head == NULL)  //initialise the head 
      { 
       firsthalf->head = malloc(sizeof(ListNode)); //create first node 
       front = firsthalf->head; 
      } 
      else 
      { 
       front->next = malloc(sizeof(ListNode));  
       front = front->next;       
      } 
      front->item = cur->item;     // insert value from list1 into firsthalf 
      cur = cur->next;       //point to next node in list1 

     } 
     front->next = NULL;  //last node 

     for (i = halfnodes; i < totalnodes; i++)    
     { 
      if (secondhalf->head == NULL) 
      { 
       secondhalf->head = malloc(sizeof(ListNode)); 
       back = secondhalf->head; 
      } 
      else 
      { 
       back->next = malloc(sizeof(ListNode)); 
       back = back->next; 
      } 
      back->item = cur->item; 
      cur = cur->next; 

     } 
     back->next = NULL; 
    } 

}

來源

2015-11-13 Katrina Lala

啊....有一些教授把這個作爲家庭作業。已經有一個答案。見http://stackoverflow.com/questions/33611261/split-linked-list/33611662#33611662 –

「但是當我反覆調用的函數，程序崩潰。」請澄清你這是用[MCVE（http://stackoverflow.com/help/mcve）表示函數是如何調用的意思。事實上，不清楚該函數的每個調用的輸入是什麼。 – kaylum

這並不真正拆分清單;它將半列表的副本創建爲兩個列表。 –

爲什麼要使用malloc？它會創建一個新的列表。但我們想分割列表。我猜firsthalf和下半年是NULL

void splitlist(LinkedList* list1, LinkedList * firsthalf, LinkedList *secondhalf)  
{ 
    ListNode *cur = list1->head; 
    ListNode *front; 
    int totalnodes = list1->size; 
    int i; 
    if (totalnodes % 2 != 0)     //if odd number of elements, add 1 to make it easier for traversal of list 
    { 
     totalnodes = totalnodes + 1; 
    } 
    int halfnodes = totalnodes/2; 

    firsthalf->head=list1->head; 
    front=firsthalf->head; 

    for(i=0;i<halfnode;i++) 
     front=front->next; 

    secondhalf->head=front->next; 
    front->next=NULL;   

}

來源

2015-11-13 11:20:16 Kalu

哦，是的，我明白你的意思。我的問題是，如果我調用splitlist（）並將另一個元素插入到list1中，並再次調用splitlist（），則前面的列表將保持不變，而backlist將爲空，表示該函數不起作用。 –

太好了！如果這清除了你的問題，請將其標記爲已刪除 – Kalu

有很多事情不對的代碼。首先malloc返回值不被檢查，malloc可能會失敗。我強烈懷疑由於malloc失敗，您的程序將停止。你在函數內部重複分配內存，但是當你不再需要的時候你是否釋放了內存？爲什麼你要使用malloc？如前所述，您不需要。

請張貼該函數的調用，因爲真的不清楚如何LinkedList* list1, LinkedList * firsthalf, LinkedList *secondhalf使用。另外還不清楚LinkedList的結構是什麼。

來源

2015-11-13 11:23:58

乍一看，我看不出你的代碼有太多錯誤（假設分配是在新的半列表中創建列表節點的副本），所以錯誤可能在於你如何調用函數，作爲例如，這可能是：

LinkedList mainlist= {0}; 
LinkedList firsthalf= {0}, secondhalf= {0}; 

//mainlist got filled somehow; we now want to split 

firsthalf->List= malloc(sizeof(ListNode)); 
secondthalf->List= malloc(sizeof(ListNode)); 
memset(firsthalf->List, 0, sizeof(ListNode)); 
memset(secondhalf->List, 0, sizeof(ListNode)); 
splitlist(&mainlist, &firsthalf, &secondhalf);

來源

2015-11-13 11:28:18

拆分鏈表到一半

回答

相關問題