#|LeetCode203. 移除链表元素链表|list|算法|链表

LeetCode203. 移除链表元素
文章目录

- LeetCode203. 移除链表元素
- - 1.题目
  - 2.思路
  - 3.具体代码实现
  - - 不使用哨兵结点
    - - （1）先特判头结点
      - （2）最后判断头结点
    - 使用哨兵结点

1.题目
【#|LeetCode203. 移除链表元素】

文章图片

2.思路
整体思路就是删去结点，但是有以下两种实现方式。

（1）不使用哨兵结点
相对来说更复杂，因为不好处理头结点，有两种思路。
a.一开始特判头结点，时间复杂度较高。
b.最后再判定头结点。
(2)使用头结点

3.具体代码实现
创建链表及函数接口

struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} }; class Solution { public: ListNode* removeElements(ListNode* head, int val) { } };

不使用哨兵结点（1）先特判头结点

class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* p =head; //指向头结点 //特判头结点 while(p!= NULL && p->val == val) { ListNode* m =p; head = head->next; p = p->next; delete m; } if(head == NULL) return nullptr; //1.NULL还是nullptr？都对ListNode* q =head; //指向头结点固定了！而且肯定不会是待删除的 while(q != NULL && q->next != NULL)//2.q!=NULL可以不写吗？可以 { if(q->next->val == val) { ListNode* n = q->next; q->next = n->next; //把链表连起来 delete n; } else//这个不能丢 q = q->next; } return head; } };

注意事项

1.return NULL/nullptr/head 都是正确的。
2.当q所指向的位置不确定是否真的存在时不能只写q->next != NULL ,必须对q的指向也有判断。
3.删除结点不能忘记把链表连起来

（2）最后判断头结点

class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* p =head; //指向头结点 ListNode* m =head; //指向头结点while(p!= NULL && p->next != NULL)//1.不能没有p！=NULL 没有判断当前指针的指向是否有意义！ { if(p->next->val == val){ ListNode* q =p->next; p->next = q->next; delete q; } else {p = p->next; } } 特判头结点 if(head != NULL && head->val == val)//最后判定头结点不为空且值为val { if(head->next != NULL)//头结点后有元素 { head = head->next; delete m; return head; } else//头结点后没有元素 { delete head; return head; //2.这里换成NULL还有nullptr都可以 } } else//头结点为空 return head; } };

注意事项

1.一定要判断当前指针的指向是否有意义！
2.return head 这里换成NULL还有nullptr都可以

使用哨兵结点

class Solution { public: ListNode* removeElements(ListNode* head, int val) { //设置一个哨兵结点 ListNode* dummyHead = new ListNode(0); dummyHead->next = head; //指向头结点 ListNode *p = dummyHead; while(p->next!= NULL) { if(p->next->val == val) { ListNode *q = p->next; p->next = q->next; delete q; }else p = p->next; } head = dummyHead->next; //不知道对不对 delete dummyHead; //不delete也行习惯应该delete return head; } };

注意事项

1.使用哨兵结点应该释放！这个习惯比较好！
2.dummyHead的创建：(按照struct里的函数）

//1. ListNode* dummyHead = new ListNode(0); dummyHead->next = head; //指向头结点//2. ListNode *dummyHead = new ListNode(0,head); //同时规定其数值和指针指向 //3. 也可以先规定指向再规定数值。