首页 > 试题广场 >

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

[编程题]从单向链表中删除指定值的节点
  • 热度指数：136649 时间限制：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

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

测试用例保证输入合法
算法知识视频讲解
添加回答
Python3
丘比特很想回家头像 丘比特很想回家 
while True:
    try:
        ls = list(map(int,input().split()))
        # [5,2,3, 2, 4, 3, 5, 2, 1, 4,3]
        ls2 = ls[2:-1] # [3, 2, 4, 3, 5, 2, 1, 4]
        res = ls[1:2]  # [2]
        for i in range(1,len(ls2),2):
            if ls2[i] in res and ls2[i-1] not in res:
                res.insert(res.index(ls2[i])+1,ls2[i-1])
                # print(res)
        res.remove(ls[-1])
        for i in res:
            print(i,end=' ')
    except:
        break

发表于 2024-12-31 23:01:24 回复(0)
Python3
doumihuoguo头像 doumihuoguo
学到了list.insert( index, value ) 的用法
按对读取新的链表节点，和旧链表中存在的节点作比较
写两个循环，外层读取新的链表节点（因为只读一次），内层用来做对比，每读取新的节点之后都要和旧点进行对比 
l = list(map(int, input().split()))
n = l[0]
listhead = l[1]
lianbiao = [listhead]
for i in range(0, 2*(n-1), 2):
    tmpl = lianbiao[:]
    for j in tmpl:
        if l[2 + i] == j:
            lianbiao.insert(lianbiao.index(j), l[3 + i])
        elif l[3 + i] == j:
            lianbiao.insert(lianbiao.index(j)+1, l[2 + i])

if len(l) == 2*n+1:
    s = l[-1]
    lianbiao.remove(s)
    print(' '.join(map(str, lianbiao)))
else:
    print(' '.join(map(str, lianbiao)))


发表于 2024-12-15 23:13:38 回复(0)
Python3
羊喵喵www头像 羊喵喵www
用列表也过了
inPut=input().strip().split()
num=inPut[0]
start_number=inPut[1]
delete_number=inPut[-1]
points=inPut[2:-1]
# print(points)
res=[]
res.append(start_number)
for i in range(1,len(points),2):
    if points[i] in res:
        res.insert(res.index(points[i])+1,points[i-1])
res.pop(res.index(delete_number))
print(' '.join(res))
发表于 2024-11-07 20:43:10 回复(0)
Python3
xlooc头像 xlooc
题解里面很多简单的一行插入代码根本就是错的，要求已有链表里面一定存在将要插入小链表的头，不知道是不是用例的问题，居然全都恰好满足，明明是没有这个条件的。 
ss=input().strip().split()

zongjiedian=int(ss[0])
toujiedian=int(ss[1])
jiedian=list(map(int,ss[2:len(ss)-1]))
shanchu=int(ss[len(ss)-1])

youtou=[]
wutou=[]
for i in range(len(jiedian)//2):
    zanshi=[jiedian[i*2],jiedian[i*2+1]]
    if toujiedian in zanshi:
        zanshi.pop(zanshi.index(toujiedian))
        youtou.append([zanshi[0],toujiedian])
    else:
        wutou.append([jiedian[i*2],jiedian[i*2+1]])

lianbiao=[toujiedian]
for ele in youtou:
        lianbiao.insert(1,ele[0])


while True:
    if len(wutou)==0:
        break
    for ele in wutou:
        wei=ele[0]
        tou=ele[1]
        if wei in lianbiao and tou in lianbiao:
            wutou.remove(ele)
            break
        elif wei in lianbiao and tou not in lianbiao:
            lianbiao.insert(lianbiao.index(wei),tou)
            wutou.remove(ele)
            break
        elif tou in lianbiao and wei not in lianbiao:
            lianbiao.insert(lianbiao.index(tou)+1,wei)
            wutou.remove(ele)
            break
lianbiao.remove(shanchu)
print(' '.join(map(str,lianbiao)))


发表于 2024-10-16 22:04:43 回复(0)
Python3
牛客908225468号头像 牛客908225468号
list1 = input().strip().split()
list_len = list1[0]
new_list = list(list1[1])
for i in range(int((len(list1[2:-1]))/2)):
    new_list.insert(new_list.index(list1[2*i+3])+1,list1[2*(i+1)])
while list1[-1] in new_list:
    new_list.remove(list1[-1])
print(' '.join(new_list))
发表于 2024-09-27 13:27:20 回复(0)
Python3
测你们码头像 测你们码
data = list(input().split())
li = []
li.append(data[1])
for i in range(2, len(data) - 1, 2):
    locate = li.index(data[i + 1])
    li.insert(locate + 1, data[i])
li.remove(data[-1])
print(" ".join(li))

发表于 2024-09-23 12:47:13 回复(0)
Python3
牛客947768359号头像 牛客947768359号
data = list(map(int, input().strip().split()))
n = data[0]
list_ = [data[1]]
for i in range(n-1):
    value = data[2*i+2]
    left = data[2*i+3]
    list_.insert(list_.index(left)+1,value)

list_.remove(data[-1])
print(*list_)
发表于 2024-09-21 07:26:48 回复(0)
Python3
祝千禧头像 祝千禧 
while True:
    try:
        s = input().split(' ')
        n, link, d = s[0], [s[1]], s[-1]
        groups = s[2:-1]
        for i in range(0, len(groups), 2):
            r, l = groups[i], groups[i+1]
            inx = link.index(l) + 1
            link = link[:inx] + [r] + link[inx:]
        dinx = link.index(d)
        link = link[:dinx]+link[dinx+1:]
        print(' '.join(link))
    except:
        break

发表于 2024-08-06 12:11:09 回复(0)
Python3
打工好难头像 打工好难 
s=list(map(int,input().split()))
list0=[s[1]]
list1=s[2:-1]
for i in range(0,len(list1)-1,2):
    list0.insert(list0.index(list1[i+1]),list1[i])
list0=list0[::-1]
for j in range(len(list0)):
    if s[-1]==list0[j]:
        list0.pop(j)
        break
print(*list0)

发表于 2024-04-27 19:22:17 回复(0)
Python3
牛客201425961号头像 牛客201425961号
用列表取巧了 
raw = list(map(int, input().split()))

l = raw[0]
lis = [raw[1]]

for i in range(l-1):
    tmp = raw[i*2+2:i*2+4]
    for j in range(len(lis)):
        if lis[j] == tmp[1]:
            lis.insert(j+1, tmp[0])
            break

for i in lis:
    if i != raw[-1]:
        print(i, end=' ')


编辑于 2024-04-10 08:58:04 回复(0)
Python3
不要香菜的小黄鸭很刻苦头像 不要香菜的小黄鸭很刻苦
python insert()和remove()真好用，还省时间 
l = list(map(int, input().split()))
n = l[0]
head = l[1]
dele = l[-1]
li = l[2:-1]
lis = []

num = [0 for i in range(n)]
num[0] = head

for i in range(0, len(li), 2):
    lis.append([li[i], li[i+1]])
    
for i in lis:
    idx = num.index(i[1])
    num.insert(idx+1, i[0])

num.remove(dele)
for i in num:
    if i != 0:
        print(i, end=' ')

发表于 2023-09-20 09:57:21 回复(0)
Python3
YM学渣头像 YM学渣
懒得构造链表，能过就行 
import sys
class L:
    def __init__(self,val=0) -> None:
        self.val = val
        self.next = None

l = input().split()

L1 = [l[1]]
rm = l[-1]
l = l[2:-1]

for i in range(1,len(l),2):
    L1.insert(L1.index(l[i]),l[i-1])
L1 = L1[::-1]
for i in range(len(L1)):
    if L1[i] == rm:
        L1.pop(i)
        break
print(' '.join(L1))



发表于 2023-07-29 16:07:30 回复(0)
Python3
牛客302708297号头像 牛客302708297号
list1 = list(map(int,input().split()))
list_lian = []
list_lian.append(list1[1])
i = 3
for x in range(list1[0]-1):
    list_lian.insert(list_lian.index(list1[i]) + 1 , list1[i-1])
    i += 2
list_lian.remove(list1[-1])
print(' '.join(map(str,list_lian)))
发表于 2023-07-16 23:01:58 回复(0)
Python3
jzhoujg头像 jzhoujg
class ListNode:
    def __init__(self, val=0,next=None):
        self.val = val
        self.next = next

nums = list(map(int,input().split()))

dummy = ListNode(-1)
node = dummy
dic = {}
node.next = ListNode(nums[1])
node = node.next
dic[node.val] = node

for i in range(1,nums[0]):
    node = dic[nums[2*i+1]]
    temp = node.next
    node.next = ListNode(nums[2*i])
    node = node.next
    node.next = temp
    dic[node.val] = node

node = dummy

while node.next:
    node = node.next
    if node.val == nums[-1]:
        continue
    print(node.val, end=' ')


   

发表于 2023-05-20 15:23:25 回复(0)
Python3
AlfredP头像 AlfredP 
class list_node:
    def __init__(self,value,next=None) -> None:
        self.value=value
        self.next=next

inputs=input().strip().split(' ')
n=inputs[0]
move=inputs[2:-1]
del_node=inputs[-1]

head=list_node(inputs[1])

for i in range(0,len(move),2):
    p=head
    new=list_node(move[i])
    while p is not None:
        if p.value==move[i+1]:
            new.next=p.next
            p.next=new
            break
        p=p.next


if head.value==del_node:
    head=head.next
else:
    p=head
    while p is not None:
        if p.next.value==del_node:
            temp=p.next
            p.next=temp.next
            temp.next=None
            break
        p=p.next

p=head
while p is not None:
    print(p.value,end=' ')
    p=p.next

发表于 2023-04-23 12:00:56 回复(0)
Python3
言旭头像 言旭 
my_list = list(map(int, input().split()))
head_list = [my_list[1]]
mid_list = my_list[2:-1]
for i in range(len(mid_list) // 2):
    head_list.insert(head_list.index(mid_list[2 * i + 1]), mid_list[2 * i])
head_list.remove(my_list[-1])
for i in head_list[::-1]:
    print(i,end=' ')

发表于 2023-03-19 15:40:36 回复(0)
Python3
你浩哥头像 你浩哥
用dict作为链表 
import sys

L = list(map(int, input().split()))

n = L[0]
first = L[1]
rm = L[-1]

head = -2
tail = -1
LL = {head: first, first:tail}

for i in range(2, len(L)-1, 2):
    a = L[i]
    b = L[i+1]
    LL[a] = LL[b]
    LL[b] = a 
# print(LL)

for x, y in LL.items():
    if y == rm:
        LL[x] = LL[rm]
        del LL[rm]
        break

cursor = LL[head]
while cursor != tail:
    print(cursor, end=' ')
    cursor = LL[cursor]


发表于 2023-03-05 14:07:15 回复(0)
Python3
客牛网hr头像 客牛网hr 
import sys

class Node:
    def __init__(self, value) -> None:
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self, head) -> None:
        self.head = head

    def add(self, target_value, before_tv):
        node = self.head
        while node.value != before_tv:
            node = node.next
        temp = node.next
        node.next=Node(target_value)
        node.next.next = temp

    def get_value_list(self):
        l = []
        node = self.head
        while node!=None:
            l.append(node.value)
            node=node.next
        return l

    def my_del(self, target_value):
        node1 = self.head
        node2 = node1.next
        while node2.value != target_vale:
            node1 = node1.next
            node2 = node2.next
        node1.next = node2.next


l = input()
l =l.split(' ')
length = l[0]
head_value = l[1]
target_vale = l[-1]
list_node = LinkedList(Node(head_value))

j = l[2:-1]
for i in range(len(j)//2):
    list_node.add(j[2*i], j[2*i+1])
list_node.my_del(target_vale)
print(" ".join(list_node.get_value_list()))
我老老实实写了个链表类
发表于 2023-03-04 21:14:40 回复(0)
提交观点

问题信息

链表
难度：
33条回答 46545浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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