DT走过的路

描述

$$定义一种单向链表的构造方法如下所示：
$\bullet$∙先输入一个整数 $n$n ，代表链表中节点的总数；
$\bullet$∙再输入一个整数 $h$h ，代表头节点的值；
$\bullet$∙此后输入 $n-1$n−1 个二元组 $(a,b)$(a,b) ，表示在值为 $b$b 的节点后插入值为 $a$a 的节点。
$$除此之外，保证输入的链表中不存在重复的节点值。

$$现在，对于给定的链表构造方法和一个额外的整数 $k$k ，你需要先按照上述构造方法构造出链表，随后删除值为 $k$k 的节点，输出剩余的链表。

输入描述：

$$在一行上：
${}_{\mathtt{\text{1.}}}$1.​先输入一个整数 $n(1\leqq n\leqq 10^3)$n(1≦n≦103) 代表链表中节点的总数；
${}_{\mathtt{\text{2.}}}$2.​随后输入一个整数 $h(1\leqq h\leqq 10^4)$h(1≦h≦104) 代表头节点的值；
${}_{\mathtt{\text{3.}}}$3.​随后输入 $n-1$n−1 个二元组 $(a,b)(1\leqq a,b\leqq 10^4)$(a,b)(1≦a,b≦104) ；
${}_{\mathtt{\text{4.}}}$4.​最后输入一个整数 $k$k ，代表需要删除的节点值。

$$除此之外，保证每一个 $b$b 值在输入前已经存在于链表中；每一个 $a$a 值在输入前均不存在于链表中。节点的值各不相同。

输出描述：

$$在一行上输出 $n-1$n−1 个整数，代表删除指定元素后剩余的链表。

示例1

输入：

5 2 3 2 4 3 5 2 1 4 3

复制

输出：

2 5 4 1

复制

说明：

$$在这个样例中，链表的构造过程如下：
$\bullet$∙头节点为 $2$2 ，得到链表 $\left[\mathbf{2}\right]$[2] ；
$\bullet$∙在 $2$2 后插入 $3$3 ，得到链表 $[2,\mathbf{3}]$[2,3] ；
$\bullet$∙在 $3$3 后插入 $4$4 ，得到链表 $[2,3,\mathbf{4}]$[2,3,4] ；
$\bullet$∙在 $2$2 后插入 $5$5 ，得到链表 $[2,\mathbf{5},3,4]$[2,5,3,4] ；
$\bullet$∙在 $4$4 后插入 $1$1 ，得到链表 $[2,5,3,4,\mathbf{1}]$[2,5,3,4,1] ；
$$随后，删除值为 $3$3 的节点，得到链表 $[2,5,4,1]$[2,5,4,1] 。

示例2

输入：

6 2 1 2 3 2 5 1 4 5 7 2 2

复制

输出：

7 3 1 5 4

复制

说明：

$$在这个样例中，链表的构造过程如下：
$\bullet$∙头节点为 $2$2 ，得到链表 $\left[\mathbf{2}\right]$[2] ；
$\bullet$∙在 $2$2 后插入 $1$1 ，得到链表 $[2,\mathbf{1}]$[2,1] ；
$\bullet$∙在 $2$2 后插入 $3$3 ，得到链表 $[2,\mathbf{3},1]$[2,3,1] ；
$\bullet$∙在 $1$1 后插入 $5$5 ，得到链表 $[2,3,1,\mathbf{5}]$[2,3,1,5] ；
$\bullet$∙在 $5$5 后插入 $4$4 ，得到链表 $[2,3,1,5,\mathbf{4}]$[2,3,1,5,4] ；
$\bullet$∙在 $2$2 后插入 $7$7 ，得到链表 $[2,\mathbf{7},3,1,5,4]$[2,7,3,1,5,4] ；
$$随后，删除值为 $2$2 的节点，得到链表 $[7,3,1,5,4]$[7,3,1,5,4] 。

采用链表结构，结构化数据

const allArr = (await readline()).split(" ").map(Number);
    //console.log(allArr,'allArr');
    const [size,headVal,...arr] = allArr
    const k = arr.pop();
    let ptr = 0;
    const hash = new Map();
    const head = new LinkNode(headVal);
    hash.set(headVal, head);
    //console.log(arr);
    for(let i=0;i<size-1;i++){
        const a = arr[ptr++];
        const b = arr[ptr++];
        
        const newNode = new LinkNode(a);
        const parentNode = hash.get(b);
        //将老的节点接入新节点后面
        newNode.next = parentNode.next;
        parentNode.next = newNode;
        hash.set(a, newNode);
    }

封装删除功能

//删除
    const removeLink=(link,delVal)=>{
        let cur = link;
        const curVal = link.val;
        if(curVal === delVal){
            link = {};
        }
       // console.log(cur,'cur');
        while(cur.next){
            const tempCur = cur.next;
            const tempVal = tempCur.val; 
            //console.log(tempCur,'tempVal');
            if(tempVal === delVal){
                //console.log("删除",delVal);
                const nextNode = tempCur.next;
                if(nextNode){
                    //console.log("删除");
                    cur.next = nextNode;
                }else{  
                    cur.next = null;
                }
            }else{
                cur = tempCur;
            }
        }
    }
    //console.log(k,'k');
    removeLink(head,k);

完整

function LinkNode(x){
    this.val = x;
    this.next = null;
}

void async function () {
    // Write your code here
    const allArr = (await readline()).split(" ").map(Number);
    //console.log(allArr,'allArr');
    const [size,headVal,...arr] = allArr
    const k = arr.pop();
    let ptr = 0;
    const hash = new Map();
    const head = new LinkNode(headVal);
    hash.set(headVal, head);
    //console.log(arr);
    for(let i=0;i<size-1;i++){
        const a = arr[ptr++];
        const b = arr[ptr++];
        
        const newNode = new LinkNode(a);
        const parentNode = hash.get(b);
        //将老的节点接入新节点后面
        newNode.next = parentNode.next;
        parentNode.next = newNode;
        hash.set(a, newNode);
    }
    //console.log(JSON.stringify(head));

    //删除
    const removeLink=(link,delVal)=>{
        let cur = link;
        const curVal = link.val;
        if(curVal === delVal){
            link = {};
        }
       // console.log(cur,'cur');
        while(cur.next){
            const tempCur = cur.next;
            const tempVal = tempCur.val; 
            //console.log(tempCur,'tempVal');
            if(tempVal === delVal){
                //console.log("删除",delVal);
                const nextNode = tempCur.next;
                if(nextNode){
                    //console.log("删除");
                    cur.next = nextNode;
                }else{  
                    cur.next = null;
                }
            }else{
                cur = tempCur;
            }
        }
    }
    //console.log(k,'k');
    removeLink(head,k);
    //console.log(JSON.stringify(head));
    const res = [];
    let itear = head;
    while(itear){
        //console.log(itear.val);
        res.push(itear.val);
        const temp = itear.next;
        itear = temp;
    }
    console.log(res.join(" "));
}()

采用数组方式

void async function () {
    let [total,head,...arr] = (await readline()).split(' ');
    let remove = arr.pop(),link = [head];
    while(arr.length){
        let [tail,head,...rest] = arr;
        arr = rest;
        let index = link.indexOf(head);
        link.splice(index+1,0,tail);
    }
    let i = link.indexOf(remove);
    link.splice(i,1);
    console.log(link.join(' '))

}()