首页 > 试题广场 >

从单向链表中删除指定值的节点

[编程题]从单向链表中删除指定值的节点
  • 热度指数：140274 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
\hspace{15pt}定义一种单向链表的构造方法如下所示：
\hspace{23pt}\bullet\,先输入一个整数 n ，代表链表中节点的总数；
\hspace{23pt}\bullet\,再输入一个整数 h ，代表头节点的值；
\hspace{23pt}\bullet\,此后输入 n-1 个二元组 \left(a, b\right) ，表示在值为 b 的节点后插入值为 a 的节点。
\hspace{15pt}除此之外，保证输入的链表中不存在重复的节点值。

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

输入描述:
\hspace{15pt}在一行上：
{\hspace{20pt}}_\texttt{1.}\,先输入一个整数 n \left(1 \leqq n \leqq 10^3\right) 代表链表中节点的总数；
{\hspace{20pt}}_\texttt{2.}\,随后输入一个整数 h \left(1 \leqq h \leqq 10^4\right) 代表头节点的值；
{\hspace{20pt}}_\texttt{3.}\,随后输入 n-1 个二元组 \left(a, b\right) \left(1 \leqq a, b \leqq 10^4\right) ；
{\hspace{20pt}}_\texttt{4.}\,最后输入一个整数 k ，代表需要删除的节点值。

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


输出描述:
\hspace{15pt}在一行上输出 n-1 个整数，代表删除指定元素后剩余的链表。
示例1

输入

5 2 3 2 4 3 5 2 1 4 3

输出

2 5 4 1

说明

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

输入

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

输出

7 3 1 5 4

说明

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

备注:
\hspace{15pt}本题由牛客重构过题面，您可能想要阅读原始题面，我们一并附于此处。
\hspace{15pt}【以下为原始题面】
输入一个单向链表和一个节点的值，从单向链表中删除等于该值的节点，删除后如果链表中无节点则返回空指针。
链表的值不能重复。
构造过程，例如输入一行数据为:
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

3 2表示为
2->3
链表为2->3->1

5 1表示为
1->5
链表为2->3->1->5

4 5表示为
5->4
链表为2->3->1->5->4

7 2表示为
2->7
链表为2->7->3->1->5->4

最后的链表的顺序为 2 7 3 1 5 4

最后一个参数为2，表示要删掉节点为2的值
删除 结点 2
则结果为 7 3 1 5 4

数据范围：链表长度满足  ，节点中的值满足 

测试用例保证输入合法
算法知识视频讲解
添加回答
我要开发烂东西头像 我要开发烂东西
自己实现链表 
import java.util.Scanner;

public class Main {
    /**
     * 输入一个单向链表和一个节点的值，从单向链表中删除等于该值的节点
     * 构造过程，例如
     * 1 2(1插入2的后面)相当于尾插发
     * 3 2（3插入2的后面）
     * 5 1（5插入1的后面）
     * 4 5
     * 7 2
     * 最后的链表的顺序为 2 7 3 1 5 4
     * 删除 结点 2
     * 则结果为 7 3 1 5 4
     * 输入描述:
     * 1 输入链表结点个数
     * 2 输入头结点的值
     * 3 按照格式插入各个结点
     * 4 输入要删除的结点的值
     */
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        while (input.hasNext()) {
            int nodeNum = input.nextInt();//插入链表节点个数
            MyNode head = null;
            MyNode curr = null;
            for (int i = 0; i < nodeNum; i++) {//循环插入nodeNum个节点
                if (i == 0){
                    head = new MyNode(input.nextInt(),null);
                    curr = head;
                }else {
                    curr = head;
                    int a = input.nextInt();
                    int b = input.nextInt();//a插到b后边
                    //找b，循环结束后还没有找到b，则直接插入最后
                    while(curr!=null){
                        if(curr.next == null){//如果找到最后一个也未发现，则直接加入到结尾
                            curr.next = new MyNode(a, null);
                            break;
                        }else if(curr.key == b){//找到b,且b不是最后一个节点
                            /*MyNode temp = new MyNode(a,null);
                            temp.next = curr.next;*/
                            curr.next = new MyNode(a, curr.next);
                            break;
                        }else {//未找到，后移一位
                            curr = curr.next;
                        }
                    }
                }
            }
            int deleteNode = input.nextInt();//要删除的节点值
            curr = head;//将curr初始化到头结点
            boolean isExists = false;//是否存在要删除的节点
            //如果删除的是头结点，则直接删除
            if(head.key == deleteNode){
                head = head.next;
                isExists = true;
            }else{//如果删除的不是头结点，则比较curr的next的key是否要删除
                while(curr.next!=null){
                    if(curr.next.key==deleteNode){
                        curr.next = curr.next.next;//删除
                        isExists = true;
                        break;
                    }
                    curr = curr.next;
                }
            }
            if(isExists){//如果删除了节点，初始化curr，遍历链表
                curr = head;
                while(curr!=null){
                    System.out.print(curr.key+" ");
                    curr = curr.next;
                }
                System.out.println();
            }
        }
    }

    static class MyNode {
        int key;
        MyNode next;

        public MyNode(int key, MyNode next) {
            this.key = key;
            this.next = next;
        }
    }
}


发表于 2020-07-26 20:13:23 回复(2)
无敌的白金之星头像 无敌的白金之星 
#include <iostream>

using namespace std;

struct ListNode
{
    int m_nKey;
    ListNode * m_pNext;
    ListNode(int key, ListNode *next = nullptr) 
        : m_nKey(key), m_pNext(next) {}
};

void insertNode(ListNode &head, int num1, int num2)
{
    ListNode *p = &head;
    while (p != nullptr && p->m_nKey != num2) 
        p = p->m_pNext;
    if (p == nullptr)
        return;
    ListNode *newNode = new ListNode(num1, p->m_pNext);
    p->m_pNext = newNode;
}

void deleteNode(ListNode &head, int num)
{
    ListNode *p = &head;
    while (p->m_pNext != nullptr && p->m_pNext->m_nKey != num)
        p = p->m_pNext;
    if (p->m_pNext == nullptr)
        return;
    ListNode *q = p->m_pNext;
    p->m_pNext = q->m_pNext;
    delete q;
}

void printList(ListNode &head)
{
    ListNode *p = &head;
    while (p != nullptr)
    {       
        cout << p->m_nKey << " ";
        p = p->m_pNext;
    }
    cout << endl;
}

int main()
{
    int n, num1, num2;
    while (cin >> n)
    {
        cin >> num1;
        ListNode head(num1);
        for (int i = 0; i < n - 1; ++i)
        {
            cin >> num1 >> num2;
            insertNode(head, num1, num2);
        }
        cin >> num1;
        deleteNode(head, num1);
        printList(head);
    }
    return 0;
}

发表于 2018-12-01 22:15:09 回复(1)
力竭的稻草人头像 力竭的稻草人 
例程有错，输入格式是将每行第一个数插入到值为第二个数的节点后面
#include <iostream>
using namespace std;
struct ListNode
{
  	int data;
    ListNode *next;
};
int main()
{
    int num ,headvalue;
    while(cin >> num >> headvalue)
    {
        ListNode *p,*head = new ListNode;
        head->data = headvalue;   //先输入第一个数
        head->next = NULL;
        int xin;
        int jiu;
        num--;
        while(num--)              //输入剩余的书
        {
            cin>>xin>>jiu;
            ListNode *q = new ListNode;
            q->data = xin;
            for(p = head; p != NULL; p = p->next)
            {
                if(p->data == jiu)
                {
                    q->next = p->next;
                    p->next = q;
                }
            }                                
        }
        int shanchu;
        cin >> shanchu;
        if(head->data == shanchu)           //要删除的是第一个节点
        {
            head->next = NULL;
        }
        for(p = head; p->next != NULL; p = p->next)     
        {
            if(p->next->data == shanchu)   
                p->next = p->next->next;
        }
        for(p = head; p != NULL; p = p->next)
        {
            cout << p->data <<" ";
        }
        cout << endl;
        
    }    
    return 0;
}

发表于 2017-03-14 19:35:52 回复(1)
忆灬逍遥头像 忆灬逍遥 

import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

// 注意输出最后有空格！
public class Main {
    public static void main(String[] args) {
	
    	Scanner sca = new Scanner(System.in);
    	while(sca.hasNext()){
    	    List<Integer> list = new LinkedList<>();
    		 int count = sca.nextInt();
    		 Integer head = sca.nextInt();
    		 list.add(head);
    		 for (int i = 0; i < count-1; i++) {
				Integer src = sca.nextInt();
				Integer temp = sca.nextInt();
				if(list.contains(src)){
					continue;
				}
				int weizhi = list.indexOf(temp);
				if(weizhi==-1){
					continue;
				}
				list.add(weizhi+1, src);
			}
    		 Integer delete =  sca.nextInt();
    		 list.remove(delete);
    		 StringBuilder sb = new StringBuilder();
    		 for (int i = 0; i < list.size(); i++) {
				sb.append(list.get(i)+" ");
			}
    		// sb = sb.deleteCharAt(sb.length()-1);
    		 System.out.println(sb.toString());
    	}
    	
    	
    	
    	
    	
    	
		
	}
}


发表于 2016-10-27 15:52:33 回复(1)
一枚小学渣头像 一枚小学渣
要支持循环输入以及输出的最后一个值后面要有空格
发表于 2015-12-31 15:24:54 回复(0)
芒硝语擦了头像 芒硝语擦了 
#include<iostream>
#include<list>
#include<algorithm>
using namespace std;
int main()
{
    int n,first_value,x,y,delete_value;
    while(cin>>n>>first_value)
    {
        list<int> l;
        l.push_back(first_value);
        for(int i=0;i<n-1;i++)
        {
            cin>>x>>y;
            auto begin=l.begin();
            auto end=l.end();
            for(;begin!=end;begin++)
            {
                if(*begin==y)
                {
                    l.insert(begin,x);
                    break;
                }
            }
            
        }
        cin>>delete_value;
        l.remove(delete_value);
        reverse(l.begin(),l.end());
        for(auto i:l) cout<<i<<" ";
        cout<<endl;
    }
}

发表于 2020-06-14 10:59:04 回复(1)
Python
ScramJet头像 ScramJet
这道题目，首先输入格式不是题目给出的那样按组输入数据，而是全部一次性输入中间带空格；另外输出格式采用join函数，最后要带一个空格，也就是输出的每个元素后面都要带空格，这个题目描述的准确，因此join一个列表最后加一个空格即可 
while True:
    try:
        s = input().split(' ')
        ls = []
        ls.append(s[1])
        m = 2
        for i in range(eval(s[0])-1):
            a,b = s[m],s[m+1]
            for j in range(len(ls)):
                if a == ls[j]:
                    ls.insert(j+1,b)
                    break
                if b == ls[j]:
                    ls.insert(j,a)
                    break
            m += 2
        ls.remove(s[-1])
        ls.reverse()
        print(' '.join(ls)+' ')
    except:
        break

发表于 2020-05-20 21:26:43 回复(5)
JavaScript V8
w布响丸辣头像 w布响丸辣 
let [total,head,...arr] = 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(' '))

发表于 2022-08-08 00:41:54 回复(0)
C
已注销头像 已注销 
#include <stdio.h>
#include <stdlib.h>
typedef struct list
{
    int num;
    struct list *next;
}list;
int main()
{
    int cnt,del,i,j;
    list *p0=malloc(sizeof(list)),*p1,*p2;
    scanf("%d%d",&cnt,&p0->num);
    p0->next=NULL;
    cnt--;
    while(cnt>0)
    {
        scanf("%d%d",&i,&j);
        p1=p0;
        while(p1!=NULL)
        {
            if(p1->num==j)
            {
                p2=malloc(sizeof(list));
                p2->num=i;
                p2->next=p1->next;
                p1->next=p2;
                break;
            }
            p1=p1->next;
        }
        cnt--;
    }
    scanf("%d",&del);
    p1=p0;
    p2=p0->next;
    if(p1->num==del)
        p0=p0->next;
    else
    {
        while(p2!=NULL)
        {
            if(p2->num==del)
            {
                p1->next=p2->next;
                break;
            }
            p1=p2;
            p2=p2->next;
        }
    }
    p1=p0;
    while(p1!=NULL)
    {
        printf("%d ",p1->num);
        p1=p1->next;
    }
    return 0;
}

发表于 2022-04-28 18:52:22 回复(0)
Java
Pickled-Rick头像 Pickled-Rick 
import java.util.*;
public class Main{
        static class Node{
            int val;
            Node next;
            Node(int val){
                this.val=val;
                this.next=null;
            }
        }
        public static void main(String[] args) {
            Scanner scanner=new Scanner(System.in);
            int n=scanner.nextInt();
            int m=scanner.nextInt();
            Node head=new Node(m);
            HashMap<Integer,Node> map=new HashMap<>();
            map.put(m,head);
            for (int i = 0; i < n-1; i++) {
                int item1=scanner.nextInt();
                int item2=scanner.nextInt();
                Node node=map.get(item2);
                Node newnode=new Node(item1);
                map.put(item1,newnode);
                if(node.next==null){
                    node.next=newnode;
                }else {
                    Node item=node.next;
                    node.next=newnode;
                    newnode.next=item;
                }
            }
            int target=scanner.nextInt();
            while (head!=null){
                if(head.val!=target){
                    System.out.print(head.val+" ");
                }
                head=head.next;
            }
        }

    }

发表于 2022-03-13 23:12:12 回复(0)
Python 3
不贵亲密贵长久，头像 不贵亲密贵长久， 
inpt = list(map(int, input().split()))
node_num = inpt[0]
head_value = inpt[1]
del_value = inpt[-1]

res = [head_value]
for i in range(2, node_num * 2, 2):
    if inpt[i] not in res:
        res.insert(res.index(inpt[i+1])+1, inpt[i])
    else:
        res.insert(res.index(inpt[i])-1, inpt[i+1])
res.remove(del_value)
for j in res:
    print(j,end=' ')
发表于 2022-02-25 11:17:29 回复(0)
Java
牛客826903958号头像 牛客826903958号
主要是读懂题目。 
//java已经封装了链表，使用LinkedList操作即可，增删效率高
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            // 5 2, 3 2 4 3 5 ,2 , 1 4, 3
            String inputStr = sc.nextLine();
            String[] strs = inputStr.split(" "); 
            String head = strs[1];// 2
            String remove = strs[strs.length - 1];//3
            List<String> list = new LinkedList();
            list.add(head);// 2
            for (int i = 2; i <= strs.length - 3; i = i+2) { //4次   3 2，4 3，5 2 ，1 4 每两数一组
                String current = strs[i+1];// 2
                String next = strs[i];// 3
                list.add(list.indexOf(current) + 1,next);
            }
            list.remove(list.indexOf(remove));// 删除 3
            System.out.println(String.join(" ",list));
        }
    }        
}


发表于 2022-01-20 14:22:15 回复(0)
C
Hey2333777头像 Hey2333777 
#include
int main()
{
    //Input number of points & value of first number
    int num;
    int fir;
    scanf("%d %d",&num,&fir);
    int sum[1000]={0};
    sum[0]=fir;

    //Input two numbers per time
    int i=1;
    while(i<num)//Times of while loop
    {
        int n1=0,n2=0;
        scanf("%d %d",&n1,&n2);

        //Detect points and input new points
        for(int j=0; j<num; j++)
        {
            if(sum[j]==n2)
            {
                //Detect whether there is a value
                if(sum[j+1]==0)
                {
                    sum[j+1]=n1;//If not, input new points
                }
                else
                {
                    for(int k=i; k>j+1; k--)
                    {
                        sum[k]=sum[k-1];//If there is, move all point back for one place
                    }
                    sum[j+1]=n1;
                }
            }
        }
        i++;
    }

    //Delete value of late number in string
    int del;
    scanf("%d", &del);
    for(int i=0; i<num; i++)
    {
        if(sum[i]==del)
        {
            for(int j=i; j<num; j++)
            {
                sum[j]=sum[j+1];//If there is a deleted point, all points behind it should move toward for one place
            }
            num--;//And number of string should minus one
        }
    }

    //Output the final string
    for(int i=0; i<num; i++)
    {
        printf("%d ",sum[i]);
    }
}
发表于 2021-12-12 23:20:53 回复(0)
Python 3
撒旦法说头像 撒旦法说
说是考链表，实则python用列表来解答 
while True:
    try:
        s=input().split()
        n=int(s[0])
        head=int(s[1])
        t=int(s[len(s)-1])

        s=[int(s[i]) for i in range(2,len(s)-1)]

        m=[]
        for i in range(0,len(s),2):
            tmp = s[i:i+2]
            m.append(tmp)

        def insert(l,x,y):
            if y in l:
                l.insert(l.index(y),x)

        l=[head]
        for i in m:
            insert(l, i[0], i[1])

        l.remove(t)
        l=l[::-1]
        for i in l:
            print(i,end=' ')
        print()
    except:
        break

发表于 2021-12-06 15:16:23 回复(0)
Python3
牛客376368287号头像 牛客376368287号
通过dict来存储节点，查询又快又方便： 
#travel
def travel_dict(list):
        key_value=list.get(-1);
        str_re='';
        while key_value!=None:
            str_re=str_re+"%d "%key_value;
            key_value=list.get(key_value);
        print(str_re.strip())

#insert
def insert_dict(list,re_num):
        value_num=list[re_num];
        list.pop(re_num);
        for k in list:
            if list[k]==re_num:
                list[k]=value_num;
        return list;

if __name__=="__main__":
    str=input();
    list_o=str.split();
    num=int(list_o[0]);
    re_num=int(list_o[-1]);
    #create dict
    list_dict=dict();
    list_dict[-1]=int(list_o[1])
    for n in range(1,num):
        e=[int(list_o[n*2+1]),int(list_o[n*2])];
        cell_num=list_dict.get(e[0]);
        if cell_num==None:
            list_dict[e[0]]=e[1];
        else:
            list_dict.pop(e[0]);
            list_dict[e[0]]=e[1];
            list_dict[e[1]]=cell_num;

    list_dict=insert_dict(list_dict,re_num);
    travel_dict(list_dict);


发表于 2021-10-27 23:16:33 回复(0)
Java
LSur头像 LSur 
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

/**
 * @author Yuliang.Lee
 * @version 1.0
 * @date 2021/9/28 18:14
 * 单向链表删除指定值的结点：
    输入一个单向链表和一个节点的值，从单向链表中删除等于该值的节点，删除后如果链表中无节点则返回空指针。
    （链表的值不会重复，且测试用例保证输入合法）

 * 示例1：
    输入：6 2 1 2 3 2 5 1 4 5 7 2 2
    输出：7 3 1 5 4
    描述：输入表示有6个节点，首节点的值为2，然后(1，2)表示在值为2的节点后添加值为1的元素，即得到2 -> 1；（3,2）即在2后添加3，得到2 -> 3 -> 1；
         （5,1）即在1的后面添加5，得到2 -> 3 -> 1 -> 5；（4,5）得到2 -> 3 -> 1 -> 5 -> 4；（7,2）得到2 -> 7 -> 3 -> 1 -> 5 -> 4
         最终的链表为：2 -> 7 -> 3 -> 1 -> 5 -> 4，需要删除的是值为2的节点，
         所以结果应为：7 -> 3 -> 1 -> 5 -> 4
 * 示例2：
    输入：5 2 3 2 4 3 5 2 1 4 3
    输出：2 5 4 1
 * 示例3：
    输入：1 5 5
    输出：null
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            // 定义链表，增删操作频繁的情况，使用LinkedList效率比较高
            List<Integer> chain = new LinkedList<>();
            // 初始化链表
            chain.add(in.nextInt());
            for (int i = 0; i < n - 1; i++) {
                int readyNode = in.nextInt();
                int existNode = in.nextInt();
                chain.add(chain.indexOf(existNode) + 1, readyNode);
            }
            // 删除指定值，注意这里与chain.remove(in.nextInt())的区别
            chain.remove(new Integer(in.nextInt()));
            // 输出
            if (chain.size() == 0) {
                System.out.println("null");
            } else {
                for (int i = 0; i < chain.size(); i++) {
                    System.out.print(chain.get(i) + (i == chain.size() - 1 ? "\n" : " "));  // 最后三目运算符这里必须加括号，并且返回的不能是字符必须是字符串
                }
            }
        }
    }
}

发表于 2021-09-28 19:03:06 回复(1)
C
胖墩墩的ssr在冲浪头像 胖墩墩的ssr在冲浪 
#include <stdio.h>
#include <string.h>
typedef struct node
{
    int _data;
    struct node* _next;
}Node;
//创建头结点
Node* creatHeadNode(int data)
{
    Node* head = (Node*)malloc(sizeof(Node));
    head->_data = data;
    head->_next = NULL;
    return head;
}
//插入节点
Node* insertNode(Node* head, int data, Node* tmp)
{
    Node* cur = (Node*)malloc(sizeof(Node));
    cur->_data = data;
    cur->_next = tmp->_next;
    tmp->_next = cur;
    return head;
}
//删除节点
Node* deletNode(Node* head, int data)
{
    Node* tmp;
    if(head->_data == data)
    {
        tmp = head->_next;
        free(head);
        return tmp;
    }
    else
    {
        tmp = head;
        while(tmp->_next->_data != data)
            tmp = tmp->_next;
        Node* cur = tmp->_next;
        tmp->_next = cur->_next;
        free(cur);
        return head;
    }
}
//查找
Node* searchNode(Node* head, int find)
{
    Node* tmp = head;
    while(tmp->_data != find)
        tmp = tmp->_next;
    return tmp;
}
int main()
{
    int arr[2000];
    int n;
    scanf("%d", &n);
    arr[0] = n;
    int len = (n-1)*2+3;
    for(int i=1;i<len; i++)
        scanf("%d", &(arr[i]));
    Node* head = creatHeadNode(arr[1]);
    for(int i=2; i<len-1; i+=2)
    {
        Node* cur = searchNode(head, arr[i+1]);
        insertNode(head, arr[i], cur);
    }
    deletNode(head, arr[len-1]);
    int th = (len-3)/2;
    Node* tmp = head;
    for(int i=0; i<th; i++)
    {
        printf("%d ", tmp->_data);
        tmp = tmp->_next;
    }
    return 0;
}

发表于 2021-08-12 23:13:28 回复(0)
Java
牛客834002708号头像 牛客834002708号 
import java.util.Scanner;
import java.util.ArrayList;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();          // 结点数
        int head = in.nextInt();       // 头节点
        ArrayList<Integer> list = new ArrayList();
        list.add(head);
        while(--n > 0){
            int next = in.nextInt();   // 待插入的结点
            int pre = in.nextInt();    // 目标结点，需要在目标结点后插入next
            if(list.indexOf(pre) < 0){ // -1表示没有这个值，直接在链表的最后插入next
                list.add(next);
            }else{                     // 找到pre结点，在pre的***入next
                list.add(list.indexOf(pre)+1,next);
            }
        }
        int targe = in.nextInt();
        list.remove((Integer)(targe)); // 删除
        for(Integer it : list){
            System.out.print(it+" ");
        }
    }
}

发表于 2021-08-12 16:10:15 回复(1)
Java
AnoxiC2010头像 AnoxiC2010 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);    
        while (in.hasNext()) { 
            int n = in.nextInt();
            Integer[] ints = new Integer[n * 2];
            for (int i = 0; i < n * 2; i++) {
                ints[i] = in.nextInt();
            }
            LinkedList<Integer> list = new LinkedList<>();
            //头节点
            list.add(ints[0]);
            //依次插入
            for (int i = 1; i < ints.length - 1; i += 2) {
                list.add(list.indexOf(ints[i + 1]) + 1, ints[i]);
            }
            //删除最后出现的
            list.remove(ints[ints.length - 1]);
            for (Integer i : list) {
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }
}

编辑于 2021-07-11 12:59:16 回复(1)
小蒋很努力头像 小蒋很努力 
 public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int num = in.nextInt();
            ListNode head = new ListNode(in.nextInt());
            for(int i = 0;i < num - 1;i++){
                ListNode newNode = new ListNode(in.nextInt());
                int curVal = in.nextInt();
                ListNode node = head;
                while(node != null){//找待插入节点的前一个节点
                    if(node.val == curVal){
                        break;
                    }else{
                        node = node.next;
                    }
                }
                if(node.next == null){//尾节点插入
                    node.next = newNode;
                }else{//中间插入
                    ListNode nex = node.next;
                    node.next = newNode;
                    newNode.next = nex;
                }
            }
            int removeVal = in.nextInt();
            //注意删除头节点
            ListNode preHead = new ListNode();
            preHead.next = head;
            ListNode cur = preHead;
            while(cur != null){
                if(cur.next.val == removeVal){
                    cur.next = cur.next.next;
                    break;
                }
                cur = cur.next;
            }
            //输出
            ListNode curHead = preHead.next;
            while(curHead != null){
                System.out.print(curHead.val + " ");
                curHead = curHead.next;
            }
            System.out.println();
        }
    }
}

class ListNode{
    int val;
    ListNode next;
    
    public ListNode(int val,ListNode next){
        this.val = val;
        this.next = next;
    }
    
    public ListNode(int val){
        this.val = val;
    }
    
    public ListNode(){
        
    }

发表于 2021-04-15 10:12:56 回复(0)
提交观点

问题信息

链表
来自：华为机试编程模拟题4
难度：
553条回答 47776浏览

热门推荐

通过挑战的用户

查看代码

相关试题

从单向链表中删除指定值的节点

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号