关于#链表#的问题，如何解决？

删除链表中的特定结点

现有一单向链表，数据域是一个整型字段，请完成删除该链表中特定节点的函数deleteList(Node *head, int n)。其中，head是链表头，n是一个整数，该函数需要删除所有数据域是n的倍数的节点，最后返回结果链表的头指针。

/*--------------------------------------------------------
注意：仅在标有"Program"和"End"的注释行之间补充填写代码。
      请勿改动主函数main和其它任何已有内容。
---------------------------------------------------------*/

#include 
using namespace std;

struct Node {
    int num;
    Node *next;
};

Node *deleteList(Node *head, int n)
{
    /**********Program**********/
    


    /**********  End  **********/
}

void printList(Node *head)
{
    Node *tmp = head;
    while(tmp)
    {
        cout << tmp->num << " ";
        tmp = tmp->next;
    }
    cout<List(int a[], int len)
{
    Node *head = NULL;
    if (len < 1)
        return head;
    
    for (int i = len-1; i >=0 ; i--)
    {
        Node *tmp = new Node;
        tmp->num = a[i];
        tmp->next = head;
        head = tmp;
    }
    return head;
}

void clearList(Node *head)
{
    Node *tmp;
    while (head)
    {
        tmp = head->next;
        delete head;
        head = tmp;
    }
}


int main()
{   
    int data[20] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10,11,12,13,14,15,16,17,18,19,20};
    Node *head = createList(data, 20);
    int n;
    cin>>n;
    head = deleteList(head, n);
    printList(head);
    clearList(head);
    return 0;
}

Node *deleteList(Node *head, int n)
{
    Node *p = head;
    Node *q = NULL;
    while(head != NULL && head->num%n==0)
    {
        p = head->next;
        free(head);
        head = p;
    }
    if(head == NULL)
        return NULL;
    while(p->next != NULL)
    {
        if(p->next->num%n==0)
        {
            q = p->next;
            p->next = q->next;
            free(q);
        }
        else
            p = p->next;
    }
    return head;
}

你可以使用以下算法来实现这个函数：

遍历链表，对于每一个节点，如果它的数据域是 n 的倍数，就将它从链表中删除。
如果删除的是头节点，就将头节点更新为下一个节点。
代码如下：

class Node {
  int data;
  Node next;
  Node(int data) {
    this.data = data;
  }
}

Node deleteList(Node head, int n) {
  // 删除头节点
  while (head != null && head.data % n == 0) {
    head = head.next;
  }

  if (head == null) {
    return null;
  }

  Node prev = head;
  Node curr = head.next;

  // 遍历剩余的节点
  while (curr != null) {
    if (curr.data % n == 0) {
      prev.next = curr.next;
    } else {
      prev = curr;
    }
    curr = curr.next;
  }

  return head;
}

这个算法的时间复杂度是 O(n)，因为它遍历了所有的节点。

供参考：

Node* deleteList(Node* head, int n)
{
    /**********Program**********/
    struct Node* pre = NULL, * ph = head;
    while (ph) {
        if (ph->num % n == 0) {
            if (pre == NULL) {
                head = head->next;
                free(ph);
                ph = head;
            }
            else {
                pre->next = ph->next;
                free(ph);
                ph = pre->next;
            }
        }
        else {
            pre = ph;
            ph = ph->next;
        }
    }
    return head;
    /**********  End  **********/
}