删除连续的元素在链表

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