华为机试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;
}


相关文章
|
2月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
22 0
LeetCode第二十四题(两两交换链表中的节点)
|
2月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
44 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
2月前
|
存储
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(一)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
05_删除链表的倒数第N个节点
05_删除链表的倒数第N个节点
|
2月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
56 0
|
2月前
|
算法 Java
数据结构与算法学习六:单向环形链表应用实例的约瑟夫环问题
这篇文章通过单向环形链表的应用实例,详细讲解了约瑟夫环问题的解决方案,并提供了Java代码实现。
25 0
|
2月前
|
存储 缓存
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)(二)
【初阶数据结构】深入解析单链表:探索底层逻辑(无头单向非循环链表)
|
6月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
6月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
6月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
65 2