题解 | #从单向链表中删除指定值的节点#

#include <iostream>
#include <forward_list>
#include <algorithm>
#include <vector>
using namespace std;

#ifdef FIRST_METHOD
/*
方法一：
思路：将头结点插入forward_list, find函数查找第一个元素，若查找到数字的位置，则下一位插入；通过remove函数删除节点。
*/
/*
void RemoveNodeFromForwardList(int num, int  head)
{
    forward_list<int> forwardList; // 创建一个单链表
    forwardList.push_front(head); // 初始化头结点
    for(int i = 1; i < num; i++) {
        int front, back;
        cin>>back>>front;
        auto iter = find(forwardList.begin(), forwardList.end(), front);
        forwardList.insert_after(iter, back);
    }
    int last;
    cin>>last; // 输入要删除的节点
    forwardList.remove(last);
    for(auto iter = forwardList.begin(); iter != forwardList.end(); iter++) {
        cout<<*iter<<" ";
    }
    cout<<endl;
}
*/
/*
方法二：
思路：将头结点插入vector, find函数查找第一个元素，若查找到数字的位置，则下一位插入；
若最后位置查找到，则直接插入；通过erase函数删除节点。
*/
void RemoveNodeFromForwardList(int num, int  head)
{
    vector<int> vec; 
    vec.push_back(head); // 初始化头结点
    for(int i = 1; i < num; i++) {
        int front, back;
        cin>>back>>front;
        auto iter = find(vec.begin(), vec.end(), front);
        if (iter != vec.end()) {
            vec.insert(iter+1, back);
        } else {
            ec.push_back(back);
        }
        
    }
    int last;
    cin>>last; // 输入要删除的节点
    vec.erase(vec.begin(), vec.end(), remove);
    for(auto iter = forwardList.begin(); iter != forwardList.end(); iter++) {
        cout<<*iter<<" ";
    }
    cout<<endl;
}

#else


/*
思路：我们也可以用正统的链表做法。构建链表，然后依次将结点插入。
插入的时候遍历链表找到插入结点的前序结点（因为表中元素互异），断开前序结点与后序结点的连接，插入结点连接后续结点，前序结点连接插入结点。
后续直接遍历链表输出，当遇到要删除的结点值时不输出即可。
*/

struct Node {
    int data;
    struct Node * next;
    Node(int x) : data(x), next(nullptr) {}
};
void RemoveNodeFromForwardList(int num, int  head)
{
     Node *pHead = new Node(head); //head = 2
     for(int i = 1; i < num; i++) {
        int pre, cur;
        cin>>cur>>pre; // cur = 1, pre =2
        Node *pCurNode = new Node(cur);
        Node *pPreNode = pHead;
        while(pPreNode->data != pre) {
            pPreNode = pPreNode->next;
        }
        pCurNode->next = pPreNode->next; // 断开
        pPreNode->next = pCurNode; //插入
    }
    int remove;
    cin>>remove;
    Node *pNewNode = pHead;
    while(pNewNode !=nullptr) {
        if(pNewNode->data != remove) {
            cout<<pNewNode->data<<" ";
        }
        pNewNode = pNewNode->next;
    }
    cout<<endl;
}
#endif

int main()
{
    int num, head;
    while(cin>>num>>head) {
        RemoveNodeFromForwardList(num, head);
    }
}