链表的面试题1
目录
第一种：递归
第二种方法就是：双指针
第三种方法：迭代
第四种：虚假哨兵位
我们来看最后一种方法：压栈
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）。除此之外，需要手动维护栈结构，代码比递归实现更复杂。
好了，以上就是主流的五种方法了，希望对你有所收获。
如果你觉得对你有帮助，可以点赞关注加收藏，感谢您的阅读，我们下一篇文章再见。
一步步来，总会学会的，首先要懂思路，才能有东西写。