刪除連續的元素在鏈表

Question

鑑於鏈表的定義如下

typedef struct elemento { 
    int inf; 
    struct elemento *next; 
} lista; 

我試圖創建一個功能

LISTA * SeekAndDestroy（LISTA * P，INT K） ;

，給定一個列表* p和一個正整數k，用於搜索該列表上，連續的元件，其總和的第一序列是完全k和消除從列表這樣的元件。

我嘗試：

lista *SeekAndDestroy(lista *p, int k) { 
    lista *a, *nuovo; 
    int x = 0; 

    a = (lista *)malloc(sizeof(lista)); 
    a->inf = p->inf; 
    nuovo = a; 
    p = p->next; 

    while (p != NULL) { 
     if (p->next != NULL) { 
      if ((p->inf + p->next->inf) == k) { 
       if (x != 1) { 
        p = p->next->next; 
        x = 1; 
        continue; 
       } 
      } 
     } 
     nuovo->next = (lista *)malloc(sizeof(lista)); 
     nuovo = nuovo->next; 
     nuovo->inf = p->inf; 
     p = p->next; 
    } 
    nuovo->next = NULL; 
    return a; 
} 

這是我的解決方案主要有兩個問題：
1）刪除最大連續兩個元素，而不是更
2）如果要刪除的項目是前兩個，該功能不起作用 我該如何解決這個問題？謝謝

Answer 1

現在讓我們忘記鏈接列表，指針和內容。說，我們必須解決給定陣列的問題。我們能做到嗎？當然！

for (int i = 0; i < array.length; ++i) { 
    for (int j = i; j < array.length; ++j) { 
     int sum = getRangeSum(array, i, j); 
     if (sum != k) continue; 

     // construct new array and return 
    } 
} 

此代碼可以進一步優化，但讓我們現在保持簡單。因此，在鏈表中，可以使用類似的方法。刪除部分也很簡單。你可以保留一個變量來跟蹤前面的節點i。我們稱之爲iParent。現在，我們可以刪除[i，j]段，如iParent->next = j->next。

顯然，你需要考慮一些極端情況一樣，如果該區段找不到或如果段從鏈表等

Answer 2

假設你的數字都是非負數，你可以使用更有效的算法。您只需通過列表運行兩個指針ptrA和ptrB，並保持包含元素的總和。

如果總和不是你需要什麼，你做兩件事之一。首先，如果您的當前總和小於所需的總和，則通過推進ptrB使下一個元素進入陣列。

如果您當前的總和爲，則您需要的數量多於，您可以通過前進ptrA取出範圍內的第一個元素。這兩種操作當然都應該調整當前的範圍總和。這裏有一個邊緣案例，如果目前只有一個項目在範圍內，您不想這樣做。

而且不言而喻，如果當前範圍總和等於您所需，您只需刪除該範圍並退出。

在僞代碼而言，這將是這樣的：

def delExact(list, desiredSum): 
    # Check non-empty and start range. 

    if list is empty: 
     return 
    ptrA = list.first 
    ptrB = ptrA 
    rangeSum = ptrA.value 

    # Continue until match found 

    while rangeSum is not equal to desiredSum: 
     # Select add-another or remove-first. 

     if ptrA == ptrB, or rangeSum < desiredSum: 
      # Need to bring another in, returning if list exhausted. 

      ptrB = ptrB.next 
      if ptrB == null: 
       return 
      rangeSum = rangeSum + ptrB.value 
     else: 
      # Need to remove one. 

      rangeSum = rangeSum - ptrA.value 
      ptrA = ptrA.next 

    # If we exit the loop, we've found a sum match. 
    # Hence we need to delete ptrA through ptrB inclusive. 

---

但是，如果負數被允許，因爲你真的不知道兩個指針的方式打破了什麼樣的影響以後的元素可能有。

在這種情況下，你基本上做一個窮舉搜索的所有可能性，這基本上可以歸結爲：

for each element in list: 
    for each possible segment from that element on: 
     check and act on summed data 

這實際上更多的英語表示，對於這樣的野獸僞代碼將沿着線：

def delExact(list, desiredSum): 
    # For each list element. 

    ptrA = list.first 
    while ptrA is not null: 
     # For each possible segment starting at that element. 

     segmentSum = 0 
     ptrB = ptrA 
     while ptrB is not null: 
      add ptrB.value to segmentSum 

      # Delete segment if sum matches, then return. 

      if segmentSum is equal to desiredSum: 
       # Here we delete from ptrA through ptrB inclusive. 
       return 

      # Otherwise, keep adding elements to segment. 

      ptrB = ptrB.next 

     # No matching segment, move on to next element. 

     ptrA = ptrA.next 

    # No matching segment at any element, just return. 

---

採用這些算法要麼將解決你唯一的問題有關刪除兩個元素。

在列表開始時刪除的問題是簡單地識別該事實（ptrA == list.first），並確保在此情況下調整指針first。這是鏈表處理中的標準邊緣情況，並且可以實現爲如下類似：

def deleteRangeInclusive(list, ptrA, ptrB): 
    # Adjust list to remove ptrA/ptrB segment, 
    # allowing for possibility ptrA may be the head. 

    if ptrA == list.first: 
     list.first = ptrB.next 
    else: 
     beforeA = list.first 
     while beforeA.next != ptrA: 
      beforeA = beforeA.next 
     beforeA.next = ptrB.next 

    # Now we can safely remove the ptrA-ptrB segment. 

    while ptrA != ptrB: 
     tempA = ptrA 
     ptrA = ptrA.next 
     delete element tempA 
    delete element ptrB 

Answer 3

這裏的開頭開始是我寫的，以解決所面臨的兩個問題的函數你和任何其他邊界條件：

list* Seek_Destroy(list* head, int target){ 
    if(head == NULL) 
     return NULL; 
    list* temp = head; 
    bool find_complete = false; 

    list *prev = temp; 
    //Loop for iterating until list is complete or target sum is found. 
    while(!find_complete){ 
     //Create a pointer for loop calculations 
     list* sum_loop = temp; 
     //Initialize sum to 0 
     int sum =0; 
     //Loop for checking whether the sum is equal to the target 
     while(sum <= target && sum_loop->next!= NULL){ 
      //Keep adding the sum 
      sum += sum_loop->inf; 

      if(sum == target){ 
       //Set the flag for exiting outer loop 
       find_complete = true; 
       //Test whether head of the list is included in the sum 
       if (temp == head){ 
        //Make head point to the struct after the last element included in the sum loop 
        head = sum_loop->next; 
        //Delete and free memory 
        while(temp!= sum_loop){ 
         list* del = temp; 
         temp = temp->next; 
         free(del); 
        } 
       }else { 
        //Set the next pointer of previous element of the list to point after the last element included in the sum loop 
        prev->next= sum_loop->next; 
        //Delete and free memory 
        while(temp!= sum_loop){ 
         list* del = temp; 
         temp = temp->next; 
         free(del); 
        } 
       }   
      break; 
      } 
      //Increment the pointer for the sum calculation   
      sum_loop = sum_loop->next; 
     } 
     prev = temp; 
     //Make temp point to next element in the list 
     temp = temp->next; 
     //IF entire list is traversed set the flag to true 
     if (temp ==NULL){ 
      find_complete = true; 
     }  
    } 

    return head; 
} 

Answer 4

我解決這樣的：

Lista *Distruggi(Lista *p, int k) { 
    Lista *n = NULL, *nuova = NULL; 
    int z = 0; 
    for (Lista *i = p; i != NULL && z != 1; i = i->next) { 
     for (Lista *j = i; j != NULL; j = j->next) { 
      int sum = somma(i, j); 
      if (sum != k) continue; 

      n = (Lista *)malloc(sizeof(Lista)); 
      n->inf = p->inf; 
      p = p->next; 
      nuova = n; 

      while (p != i) { 
       nuova->next = (Lista *)malloc(sizeof(Lista)); 
       nuova = nuova->next; 
       nuova->inf = p->inf; 
       p = p->next; 
      } 

      while (j != NULL) { 
       nuova->next = (Lista *)malloc(sizeof(Lista)); 
       nuova = nuova->next; 
       nuova->inf = j->inf; 
       j = j->next; 
      } 
      z = 1; 
      break; 
     } 
    } 
    if (z == 0) return p;//NO CHANGE 
    else {//CHANGE 
     nuova->next = NULL; 
     return n; 
    } 
}