题目描述
输入一个单向链表和一个节点的值,从单向链表中删除等于该值的节点,删除后如果链表中无节点则返回空指针。
6 2 1 2 3 2 5 1 4 5 7 2 2
则第一个参数6表示输入总共6个节点,第二个参数2表示头节点值为2,剩下的2个一组表示第2个节点值后面插入第1个节点值,为以下表示:
1 2 表示为
2->1
链表为2->1
方法1:
用c++的stl库,其中用vector也可以,但是vector是连续空间的,所以为了更符合题意选择了list。
插入时,通过迭代器找到元素的位置,然后在后面insert数组。
删除时,也是通过迭代器找到元素的位置,erase删除。
也就是删除和插入都需要位置信息pos。
//两个一组 a b 表示b后面插入a #include<iostream> #include<list>//stl库,list是双向链表 using namespace std; int main(){ int num,head; cin>>num>>head; list<int> mylist; mylist.push_front(head);//在开头放入头结点 list<int>::iterator it; for(int i=0;i<num-1;i++){ int a,b; cin>>a>>b; for(it=mylist.begin();it!=mylist.end()&&*it!=b;it++);//遇到等于b时候停止,it指向b元素 mylist.insert(++it,a);//注意是在b的后面插入a,所以++it } int k; cin>>k; for(it=mylist.begin();it!=mylist.end()&&*it!=k;it++);//找到k目标元素的位置 mylist.erase(it); for(it=mylist.begin();it!=mylist.end();it++)//输出链表内容 cout<<*it<<' '; }
方法2:
自己写链表
//两个一组 a b 表示b后面插入a #include<iostream> using namespace std; struct ListNode { int val; ListNode* next = nullptr; }; class list { public: ListNode* creat(int firstmem) {//给出第一个结点的数据域,返回头结点(头结点不存储数据) ListNode* head = new ListNode; head->next = new ListNode; head->next->val = firstmem; return head; } void insert(ListNode* head, int a, int b) {//在b后面插入a ListNode* p = head->next;//要从第一个结点开始搜索 while (p && p->val != b) p = p->next; ListNode* q = new ListNode; q->val = a; q->next = p->next; p->next = q; } void erase(ListNode* head, int k) {//删除k ListNode* p = head;//要从第一个结点的前一个开始搜索 while (p && p->next->val != k) p = p->next; ListNode* q = p->next; p->next = p->next->next; delete(q); } void print(ListNode* head) {//打印链表内容 ListNode* p = head->next; while (p) { cout << p->val << ' '; p=p->next; } } }; int main() { int num, headnum; cin >> num >> headnum; list L; ListNode* head = L.creat(headnum);//创建链表 for (int i = 0; i < num-1; i++) { int a, b; cin >> a >> b; L.insert(head,a,b);//添加结点 } int k; cin >> k; L.erase(head,k);//删除结点 L.print(head);//打印结点数据域 }