让我挠头的计算机难题（单链表的增删查改）

在这里插入图片描述

一.移除链表元素

移除链表元素

在这里插入图片描述

整体思路为创建一个新的链表 ，遍历原链表，如果该元素是我所需的元素，则把他保存在新的链表之中，否则跳过该节点。尾节点指针始终在链表尾部。另外要注意的两种情况，一种是当原链表为空的时候，这是要直接返回的是空指针，也就是未经过处理的newhead;另外一种情况是当原链表最后一位元素是所要删除的元素时，要单独拿出来处理，因为经最后一位元素时，尾指针的指向是释放内存之后的原最后一位元素地址，而不是空指针。所以要将最后尾指针的下一位指向空指针。

1.变量初始化

newhead 和 newtail 用于构建新的链表，初始都设为 NULL。 pcur 作为遍历原链表的指针，初始指向原链表的头节点 head。

2.遍历原链表

使用 while(pcur) 循环，只要 pcur 不为 NULL，就持续遍历原链表。

3.节点筛选

对于当前节点 pcur，若其值不等于 val，说明该节点要保留在新链表中： 若 newhead 为 NULL，意味着新链表还没节点，就把 pcur 作为新链表的头节点和尾节点，即 newhead = newtail = pcur。 若 newhead 不为 NULL，表明新链表已有节点，把 pcur 接到新链表尾部，即 newtail->next = pcur，然后更新尾节点 newtail = newtail->next。

4.指针移动

无论当前节点是否保留，都将 pcur 指针向后移动一位，即 pcur = pcur->next。

5.处理新链表尾节点

遍历结束后，若 newtail 不为 NULL，将其 next 指针置为 NULL，保证新链表以 NULL 结尾。

6.返回结果

最后返回新链表的头节点 newhead

 typedef struct ListNode ListNode;
struct ListNode* removeElements(struct ListNode* head, int val) {
    ListNode* newhead,* newtail;
    newhead = newtail = NULL;
    ListNode* pcur = head;
    while(pcur)
    {
        if(pcur->val != val)
        {
            if(newhead == NULL)
            {
                newhead = newtail = pcur;
            }
            else
            {
                newtail->next = pcur;
                newtail = newtail->next;
            }
        }
        pcur = pcur->next;
    }
    if(newtail != NULL)
    {
        newtail->next = NULL;
    }
    return newhead;
}

二.反转链表

反转链表

在这里插入图片描述

解决反转链表的必备操作，使用三个指针来逐步反转链表。这种方法简单且高效，时间复杂度为 O(n)，空间复杂度为 O(1)。遍历链表，逐步让后一个结构体指针指向前一个元素。

1.边界条件处理：

◦ 如果输入的链表为空（即 head == NULL），直接返回 NULL。这是合理的，因为空链表反转后仍然是空链表。

2. 初始化指针：

◦ n1 初始化为 NULL，表示反转后链表的当前尾部（初始时为空）。 ◦ n2 初始化为 head，表示当前正在处理的节点。 ◦ n3 初始化为 head->next，表示下一个待处理的节点。

3. 反转链表：

◦ 使用 while (n2) 循环，直到所有节点都被处理完。 ◦ 在每次循环中： 将 n2->next 指向 n1，实现当前节点的反转。 更新 n1 为 n2，将 n2 移动到 n3，并将 n3 移动到下一个节点（如果存在）。 ◦ 这种方式逐步将链表的节点反转，同时保持链表的连续性。

4. 返回结果：

◦ 最终返回 n1，即反转后的链表头指针

typedef struct ListNode ListNode;
struct ListNode* reverseList(struct ListNode* head) {
    if(head == NULL)
    return NULL;
    ListNode* n1 , * n2, * n3;
    n1 = NULL;
    n2 = head;
    n3 = head->next;
    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3)
        n3 = n3->next;
    }
    return n1;
}

三.链表的中间节点

链表的中间节点

在这里插入图片描述

通过快慢指针法高效地找到了链表的中间节点，时间复杂度为 O(n)，空间复杂度为 O(1)。

快慢指针是一种非常实用高效的解题方法，慢指针一次移动一步，快指针一次移动两步，当快指针走到结尾时，由于速度是慢指针的两倍，所以慢指针此时在链表的中部节点。

要注意的是判断循环的条件 fast 与 fast->next 的位置不能互换，原因是若fast为空时，若fast->next在前，则会造成对空指针的解引用。

1.指针变量：

◦ 定义了两个指针变量 show 和 fast，它们都初始化为链表的头节点 head。 ◦ show 是慢指针，每次移动一步。 ◦ fast 是快指针，每次移动两步。

2. 循环条件：

◦ while(fast && fast->next)：这个条件确保在遍历链表时不会出现空指针解引用的问题。 ◦ fast 不能为 NULL，否则无法访问 fast->next。 ◦ fast->next 也不能为 NULL，否则无法访问 fast->next->next。

3. 指针移动：

◦ 在循环中： ■ show = show->next：慢指针每次向前移动一步。 ■ fast = fast->next->next：快指针每次向前移动两步。

4. 循环结束条件：

◦ 当 fast 或 fast->next 为 NULL 时，循环结束。 ◦ 此时，show 指向的就是链表的中间节点。

5. 返回值：

◦ 返回 show，即链表的中间节点

 typedef struct ListNode ListNode;
struct ListNode* middleNode(struct ListNode* head) {
    ListNode* show , * fast;
    show = fast = head;
    while(fast&&fast->next)
    {
        show = show->next;
        fast = fast->next->next;
    }
    return show;
}