- 题目:
- ⌛ 总体思路:
- 方法①-无哨兵结点的遍历
- 方法②-有哨兵结点的遍历
- 方法③-尾插新链表
- 方法④-递归
- 附:单链表调试数据
203. 移除链表元素【难度:简单】
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val的节点,并返回新的头节点
- 示例 1:
输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]
- 示例 2:
输入:head = [], val = 1
输出:[]
- 示例 3:
输入:head = [7,7,7,7], val = 7
输出:[]
提示:
- 列表中的节点数目在范围 [0, 104] 内
- 1 <= Node.val <= 50
- 0 <= val <= 50
遍历链表,一一比较结点的val是否为要删除的。若为要删除的结点:先释放掉此结点,再将此结点的上一结点链接到此结点的下一结点
方法①-无哨兵结点的遍历 思路:
定义一个cur:表示指向要删的元素结点;
定义一个prev:表示要删的元素的前面的结点;
区分头删和非头删的情况,头删则修改头指针的指向。
先让prev的next指向cur的next;再释放cur;同时,cur要继续迭代往前走,找是否还有要删除的元素,此时让cur指向prev的next即可;
如果链表为空,直接返回空指针;
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* cur = head,*prev = NULL; while(cur) //遍历到要删除的结点 { if(cur->val == val) { // 1.头删 2.非头删 if(cur == head) //头删单独处理 { head = head->next; //修改头指针的指向,不在指向头结点 free(cur); cur = head; } else { prev->next = cur->next; free(cur); cur = prev->next; } } else { prev = cur; cur = cur->next; } } // 当退出循环表示cur到尾结点 空链表则不进入循环直接返回 return head; }
这里传参我们注意到,修改了头指针好像并没有用二级指针传参诶,但又成功了,为什么呢❓
struct ListNode* removeElements(struct ListNode* head, int val) { ...... return head; }
原因就在这里,返回了新的头指针
方法②-有哨兵结点的遍历 思路:相比于没有哨兵结点的迭代,有哨兵结点的遍历可以不区分头删与非头删。
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* cur = head; struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* tail = guard; while(cur) { if(cur->val != val) { tail->next = cur; tail = tail->next; cur = cur->next; } else { struct ListNode* del = cur; cur = cur->next; free(del); } } // 最后节点是val,就会出现此问题 if(tail) tail->next = NULL; head = guard->next; free(guard); return head; }
⌛ 小结:
替代我们之前实现的二级指针的方法:
- 返回新的链表头
- 设计为带哨兵位的
思路:把不是val的结点尾插到新链表,然后返回新链表
struct ListNode* removeElements(struct ListNode* head, int val) { struct ListNode* cur = head; struct ListNode* newhead = NULL, *tail = NULL; while(cur) { if(cur->val != val) { if(tail == NULL) { newhead = tail = cur; } else { tail->next = cur; tail = tail->next; } cur = cur->next; } else { struct ListNode* del = cur; cur = cur->next; free(del); } } // 最后节点是val,就会出现此问题 if(tail) tail->next = NULL; return newhead; } 方法④-递归
思路:要删除val,返回头结点;
那么我们就递归删除head->next即可得到一个新的结点newNode;
这个结点就是删除完后的结点;用head->next链接newNode;
然后再判断head头结点是否要删除的值:不是就直接返回head,是的就直接返回head->next(即newNode结点)
struct ListNode* removeElements(struct ListNode* head, int val) { if(!head ) return NULL; //要删除链表中的结点:也就是删除head->next的结点 struct ListNode* newNode = removeElements(head->next,val); head->next = newNode; //头结点连接删好后的链表 return head->val == val ? head->next : head; //判断头节点的值是否和要删的val相同 } 附:单链表调试数据
做题一定要画图+调试,备一份数据以后方便在VS里面调试
int main() { struct ListNode* n1 = malloc(sizeof(struct ListNode)); assert(n1); struct ListNode* n2 = malloc(sizeof(struct ListNode)); assert(n2); struct ListNode* n3 = malloc(sizeof(struct ListNode)); assert(n3); struct ListNode* n4 = malloc(sizeof(struct ListNode)); assert(n4); struct ListNode* n5 = malloc(sizeof(struct ListNode)); assert(n5); struct ListNode* n6 = malloc(sizeof(struct ListNode)); assert(n6); struct ListNode* n7 = malloc(sizeof(struct ListNode)); assert(n7); n1->next = n2; n2->next = n3; n3->next = n4; n4->next = n5; n5->next = n6; n6->next = n7; n7->next = NULL; n1->val = 1; n2->val = 2; n3->val = 6; n4->val = 3; n5->val = 4; n6->val = 5; n7->val = 6; struct ListNode* head = removeElements(n1, 6); return 0; }