链表的面试题1-CSDN博客

本文链接：https://blog.csdn.net/chenyuhao2024/article/details/147700290

https://leetcode.cn/problems/remove-linked-list-elements/description/

这道题的话我们看到需要删除节点，那很自然就能想到这其中一定要用到遍历的想法。但是链表这个数据结构有一个很明显的特点，就是递归性。这里借用一下大佬的图（免责说明）

第一种：递归

递归递归，不就是先递推，再回归吗？那干脆先像图里说的一样写，那就是这样

struct ListNode* removeElements(struct ListNode* head, int val){ 
    if (NULL == head) {
        return head;
    }     

    /* 删除头节点后所有值为 val 的节点 */
    struct ListNode* res = removeElements(head->next, val);

    /* 头节点是待删除的节点 */
    if (head->val == val) {
        return res;
    /* 头节点不是待删除的节点，头节点后面挂接已处理的链表（更短的） */
    } else {
        head->next = res;
        return head;
    }

我们在化简，用上while和三元条件运算符，那就是这样：

struct ListNode* removeElements(struct ListNode* head, int val){ 
    if (NULL == head) {
        return head;
    }     

    head->next = removeElements(head->next, val);
    return head->val == val ? head->next : head;
}

第二种方法就是：双指针

我们什么时候会用到双指针最多呢？是不是循环队列？那我们那时候是为了解决什么问题采用上双指针的呢?

我们是不是为了解决，进队列和出队列的问题的优化我们的时间复杂度才用双指针的？具体就可以看一下栈的应用，为什么只用一个栈顶指针？因为人家只有一个出入口，所以一个保安就够了啊。这样说就很容易理解了。

思路：设置两个均指向头节点的指针，pre（记录待删除节点的前一节点）和 cur (记录当前节点)；

遍历整个链表，查找节点值为 val 的节点，找到即删除该节点，否则继续查找。

2.1 找到，将当前节点的前一节点（之前最近一个值不等于 val 的节点(pre)）连接到当前节点（cur）的下一个节点（即将 pre 的下一节点指向 cur 的下一节点：pre->next = cur->next）。

2.2 没找到，更新最近一个值不等于 val 的节点（即 pre = cur），并继续遍历（cur = cur->next）。

struct ListNode* removeElements(struct ListNode* head, int val){
    while (NULL != head && head->val == val) {
        head = head->next;
    }
    
    struct ListNode* cur = head;
    struct ListNode* pre = head;
    while (cur != NULL) {
        if (cur->val == val) {
            pre->next = cur->next;
        } else {
            pre = cur;
        }
        cur = cur->next;
    }
    return head;
}

第三种方法：迭代

首先我觉得很有必要和大家再来看一下迭代和递归的区别：递推是调用自身递推回归，而迭代很像我们初学while循环的时候的循环图，也就是说，如果我现在给你一个a=0，如果小于10，那就得迭代a++这句句子好多次才可以达到跳出循环。

好，那么我们看回这道题。

删除链表中给定值的节点，一般的步骤是：

遍历链表，找到所有值为 val 的节点；

将值为 val 的节点的上一个节点直接指向该节点的下一个节点（pre->next = pre->next->next）。

等于我们重复的是什么工作？是判断，然后连接，本质上和递归没有什么区别。

在这里放一下代码，接下去还有两种非常巧妙的方法，讲究一个知识的串通。

struct ListNode* removeElements(struct ListNode* head, int val){
    while (NULL != head && head->val == val) {
        head = head->next;
    }

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

    struct ListNode* pre = head;
    while (pre->next != NULL) {
        /* 找到值为 val 的节点，并将其删除 */
        if (pre->next->val == val) {
            pre->next = pre->next->next;   
        } else {
            /* 没找到，则继续遍历查找 */
            pre = pre->next;
        }
    }
    return head;
}

第四种：虚假哨兵位

前三种方法均需要判断头节点是否为待删除的节点，且处理头节点的代码逻辑与其它节点特别相似，有没有方法使得代码更优美并且能避免对头节点的判断呢？

答案是有的。可以通过在头节点前增加虚拟头节点，这样头节点就成了普通节点，不需要单独拎出来考虑，但是在返回的时候，返回的是虚拟头节点的下一节点而不是虚拟头节点。

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (NULL == dummyHead) {
        return NULL;
    }

    dummyHead->next = head;
    struct ListNode* cur = dummyHead;
    while (cur->next != NULL) {
        if (cur->next->val == val) {
            ListNode* delNode = cur->next;
            cur->next = delNode->next;
            free(delNode);
        } else {
            cur = cur->next;
        }
    }

    struct ListNode* retNode = dummyHead->next;
    free(dummyHead);
    return retNode;
}

对于这种独辟蹊径的方法，我们重点不应该是想我怎么没有想到这种方法。更应该思考的是，为什么会想到这种方法，这种方法有什么优缺点。那我们就来讨论。

用上这个哨兵位的节点可以避免对头节点的格外讨论，而且所需要开辟的空间只是一个节点的空间，就是O（1），时间复杂度是O（n），效率是极高的。但是需要注意的一点是什么？如果最后哨兵位头节点不释放，那就会造成我们之前所说的内存泄露。而你用迭代和递归则是要把头节点单独讨论，并且还要开辟空间。

struct ListNode* removeElements(struct ListNode* head, int val){
    struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    if (NULL == dummyHead) {
        return NULL;
    }

    dummyHead->next = head;
    struct ListNode* cur = dummyHead;
    while (cur->next != NULL) {
        if (cur->next->val == val) {
            ListNode* delNode = cur->next;
            cur->next = delNode->next;
            free(delNode);
        } else {
            cur = cur->next;
        }
    }

    struct ListNode* retNode = dummyHead->next;
    free(dummyHead);
    return retNode;
}

我们来看最后一种方法：压栈

本题还可以采用栈去做。

将值不等于 val 的节点依次压入栈中；

将压入栈的节点重新连接，栈底的节点作为新的头节点返回。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        Stack<ListNode> stack = new Stack<ListNode>();
        while (null != head) {
            if (head.val != val) {
                stack.push(head);
            }
            head = head.next;
        }

        while (!stack.isEmpty()) {
            stack.peek().next = head;
            head = stack.pop();
        }
        return head;
    }
}

为什么要压栈？因为迭代压栈的效率比递归高，没有函数调用的开销。当然我们在这里如果严谨一点说的话，显式栈结构还是比较复杂的，空间复杂度是O（n）。除此之外，需要手动维护栈结构，代码比递归实现更复杂。

好了，以上就是主流的五种方法了，希望对你有所收获。

如果你觉得对你有帮助，可以点赞关注加收藏，感谢您的阅读，我们下一篇文章再见。

一步步来，总会学会的，首先要懂思路，才能有东西写。