华为机试HJ48:从单向链表中删除指定值的节点

简介: 华为机试HJ48:从单向链表中删除指定值的节点

题目描述:

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


链表的值不能重复。


构造过程,例如输入一行数据为:


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


链表长度不大于1000,每个节点的值不大于10000。


测试用例保证输入合法

输入描述:

输入一行,有以下4个部分:

1 输入链表结点个数

2 输入头结点的值

3 按照格式插入各个结点

4 输入要删除的结点的值

输出描述:

输出一行

输出删除结点后的序列,每个数后都要加空格

示例:

输入:

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


解题思路:

这道题正常就是用链表或vector以及指针来做,插入删除即可。在牛客看到有个西南交通大学的大佬“MccreeHero”分享了一个静态链表的方法,我觉得挺好的,特此分享给大家。


它的思路是用数组存放数据,数据不仅代表着数值,也表示下个数据的下标,比如2存放在a[0],若2指向5,那么a[2]存放的就是5,该方法的插入时间复杂度为O(1),删除的时候需要遍历查找一遍,查找复杂度为O(n),删除的时候,将存放删除数的位置更换数值为a[删除数]的值,比如删除3,原本a[5]等于3,a[3]等于4,那么删除后a[5]等于4,相当于跳过了3;最后,再用下标法从0开始遍历一遍即可。

测试代码:

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int n, head;
    int a[10000];
    while (cin >> n >> head) {
        fill(a, a + 10000, -1);
        a[0] = head;
        for (int i = 1; i < n; i++) {
            int cur, pre;
            cin >> cur >> pre;
            int nx = a[pre];
            a[pre] = cur;
            a[cur] = nx;
        }
        int del;
        cin >> del;
        int pHead = 0, pcur = pHead;
        while (pcur != -1) {
            int nx = a[pcur];
            if (nx == del) 
                a[pcur] = a[nx];
            else 
                pcur = a[pcur];
        }
        pcur = pHead;
        while (a[pcur] != -1) {
            cout << a[pcur] << " ";
            pcur = a[pcur];
        }
        cout << endl;
    }
    return 0;
}


相关文章
05_删除链表的倒数第N个节点
05_删除链表的倒数第N个节点
04_两两交换链表中的节点
04_两两交换链表中的节点
|
2月前
|
算法
LeetCode第24题两两交换链表中的节点
这篇文章介绍了LeetCode第24题"两两交换链表中的节点"的解题方法,通过使用虚拟节点和前驱节点技巧,实现了链表中相邻节点的交换。
LeetCode第24题两两交换链表中的节点
|
2月前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案,使用双指针法找到并返回链表中倒数第k个节点。
42 5
|
2月前
|
Python
【Leetcode刷题Python】剑指 Offer 18. 删除链表的节点
Leetcode题目"剑指 Offer 18. 删除链表的节点"的Python解决方案,通过使用双指针法找到并删除链表中值为特定数值的节点,然后返回更新后的链表头节点。
33 4
|
2月前
|
存储 JavaScript 前端开发
JavaScript实现单向链表
JavaScript实现单向链表
17 0
|
4月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
4月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
4月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
32 2
|
5月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
46 1