首页 > 试题广场 >

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

[编程题]从单向链表中删除指定值的节点
  • 热度指数：123514 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

输入一个单向链表和一个节点的值，从单向链表中删除等于该值的节点，删除后如果链表中无节点则返回空指针。

链表的值不能重复。

构造过程，例如输入一行数据为:
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

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

测试用例保证输入合法



输入描述:
输入一行，有以下4个部分：

1 输入链表结点个数
2 输入头结点的值
3 按照格式插入各个结点
4 输入要删除的结点的值


输出描述:
输出一行

输出删除结点后的序列，每个数后都要加空格
示例1

输入

5 2 3 2 4 3 5 2 1 4 3

输出

2 5 4 1

说明

形成的链表为2->5->3->4->1
删掉节点3，返回的就是2->5->4->1
示例2

输入

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

输出

7 3 1 5 4

说明

如题
算法知识视频讲解
添加回答
Python
辣条虾头像 辣条虾 
"""
[说明]：
    1，本题的输入格式有问题，实际输入格式是将各元素在一行进行输入！！！
        比如例子中的输入格式为：5 2 3 2 4 3 5 2 1 4 3
    2，每组例子输出完成（在每个字符后都要加空格）后，还需要加上单独的一个换行！！！

    3，题目中的->符号表示按照顺序插入
        例如，2->1，2->3，2->7，表示先 2->1，然后 2->3->1，最后 2->7->3->1
    
    4，其他的就和常规链表删除结点操作一样了，下面用数组进行处理。
"""
class Solution:
    def fun(self, head, target, arr):
        # 用来存储整个链表的最终表示（未删除前），例如，2->5->3->4->1
        ans = [head]
        for num in arr:
            idx = ans.index(num[1])   # 找到当前结点在ans中的位置
            ans.insert(idx+1, num[0])  # 再将当前结点的下一个结点插入到ans中的下一个位置
        # 找到要删除结点的位置
        tmp = ans.index(target)
        # 删除目标结点
        ans.pop(tmp)
        return ans
    
if __name__ == '__main__':
    while True:
        try:
            # 题目中的输入是将所以元素在同一行输入，同时中间用空格
            tmp = list(map(int, input().split()))
            # 结点总个数
            n = tmp[0]
            # 头结点
            head = tmp[1]
            # 需要删除的目标结点
            target = tmp[-1]
            # 将各结点的链接重新处理一下，例如，arr = [[3,2], [4,3], [5,2], [1, 4]]
            tmp = tmp[2:len(tmp)-1]
            arr = []
            for i in range(len(tmp)//2):
                arr.append([tmp[2*i], tmp[2*i+1]])
            ans = Solution().fun(head, target, arr)
            for i in range(len(ans)):
                print(str(ans[i]), end=' ')
            # 在每一个例子输出完后，还要加上一个换行！！！
            print()
        except:
            break

编辑于 2021-01-17 20:57:37 回复(0)
TheSRE头像 TheSRE 
while True:
    try:
        s = input().split()
        num = int(s[0])
        res = [s[1]]
        for i in range(num - 1):
            a = s[2 + i * 2]
            b = s[3 + i * 2]
            res.insert(res.index(b) + 1, a)
        rm = s[-1]

        res.remove(rm)
        print(' '.join(res) + ' ')
    except:
        break
先用单向链表，明明打印了，却显示空。看了一下别人的答案，用列表就可以解决，很妙！
发表于 2019-11-17 11:10:31 回复(0)
我要开发烂东西头像 我要开发烂东西
自己实现链表 
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)
C/C++
牛客227521256号头像 牛客227521256号 
#include <stdio.h>

typedef struct Node{
    int key;
    struct Node * Next;
}ListNode;

void insert(ListNode *n, int d,int e)
{
    ListNode *p,*q;
	p = (ListNode *)malloc(sizeof(ListNode));
	p->key = e;
	q = n;
	while(q->Next)
	{
		if(q->key == d)	
			break;
		q = q->Next;
	}
	p->Next = q->Next;
	q->Next = p;	
}

int delete(ListNode **n, int e)	//用二级指针来修改原来传进来的地址 
{
	ListNode *p,*q;
	q = *n;
	if(q->key == e)
	{
		*n = q->Next; 
		free(q);
		return 1;
	}
	while(q->Next)
	{
		if(q->Next->key == e)	
		{
			p = q->Next; 
			q->Next = p->Next;
			free(p);
			return 1;
		}
		q = q->Next;
	}
	return 0;
}

int main()
{
    int i,n,e,d;
    while(scanf("%d",&n) != EOF )
    {
  	 	ListNode *q,*p = (ListNode *)malloc(sizeof(ListNode));
        scanf("%d",&e);
        p->key = e;
        p->Next = NULL;
        for(i=0; i<n-1; i++)
        {
            scanf("%d %d",&e,&d);
            insert(p, d, e);
        }
        scanf("%d",&e);
        delete(&p,e);
		while(p)
		{
			q = p->Next;
			printf("%d ",p->key);
			free(p);
			p = q;
		}
		putchar('\n');  
    }
    return 0;
}

发表于 2020-04-06 22:16:41 回复(2)
芒硝语擦了头像 芒硝语擦了 
#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)
提交观点

问题信息

链表
难度：
493条回答 44228浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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