程序员经验分享-hwhale

C语言 | NowCoder链表题解

2023-05-16

目录

  • 前言
  • 1.单向链表
  • 2.链表交换
  • 3.单链表求和
  • 4.双链表求和
  • 5.链表删除
  • 6.链表添加结点
  • 7.反转链表

前言

题目来源于 https://www.nowcoder.com/exam/oj?page=1

1.单向链表

描述

从键盘输入一个长度为 n 的数组，问你能否用这个数组组成一个链表，并顺序输出链表每个节点的值。

输入描述

第一行输入一个正整数 n ，表示数组的长度

输出描述

制作一个链表然后输出这个链表的值

示例

  • 输入
    4
    5 4 2 1
  • 输出
    5 4 2 1

题解

#include <stdio.h>
#include <stdlib.h>

typedef struct Node     //链表的结构体
{
    int data;           //数据域，可以是任何类型的数据
    struct Node *next;  //指针域
}Node;                  //链表就是：这样的结构体的变量连接在一起

//用一个指针表示一个链表
Node *create_list()
{
    Node *head_Node = (Node*)malloc(sizeof(Node)); //用一个指针去表示一个表头，headNode变成了结构体变量
    //变量使用前，必须被初始化
    head_Node->next = NULL;
    return head_Node;
}

//创建节点，节点就是结构体变量，只是说我们在创建过程中用指针去表示
//和创建链表的区别是：多一个数据域
Node *create_node(int data)
{
    Node *new_Node = (Node*)malloc(sizeof(Node));//用指针去表示节点
    //初始化
    new_Node->data = data;
    new_Node->next = NULL;
    return new_Node;
}

//打印函数
//打印节点,一般头节点不存放数据，打印从第二个开始，定义一个额外的结构体指针去打印它
void print_list(Node *head_Node)
{
    Node *pMove = head_Node->next; //头指针指向第二个节点，从第二个节点开始打印
    while(pMove)                   //当节点不空
    {
        printf("%d ",pMove->data);
        pMove = pMove->next;
    }
}

//插入函数
//头插法,通过头部的方式（插到以头节点表示的链表，插入的节点数据）
//头插法，数据输入是倒过来的！！！
void insert_Node_by_Head(Node *headNode,int data)
{
    //1、创建插入的节点（用创建节点的子函数）
    Node *new_Node = create_node(data);
    //2、新的节点 = 上一个节点的next，连到下一个节点，上一个节点的next = 连到新的节点
    new_Node->next = headNode->next;
    headNode->next = new_Node;
}

//尾插法
void insert_Node_by_Tail(Node *headNode, int data)
{
    //1、创建插入的节点（用创建节点的子函数）
    Node *new_Node = create_node(data);
    //2、创建一个探测变量，从头节点探到底
    Node *test_Node = NULL;
    for(test_Node = headNode; test_Node->next != NULL ; test_Node = test_Node->next);
    //3、这个尾部节点数据 填入 新节点的地址
    test_Node->next = new_Node;
}

int main()
{
    //动态链表：用指针去动态申请内存，变成结构体变量
    //动态创建一个链表：动态内存申请+模块化设计
    //1、创建链表（创建一个表头，表示整个链表）
    //2、创建节点
    //3、插入节点
    //4、删除节点
    //5、打印 遍历链表
    int n;
    int a[100];
    Node *list = create_list();
    while((scanf("%d", &n) != EOF))
    {
        for(int i = 0 ; i < n ; i++)
        {
            scanf("%d", &a[i]);
            insert_Node_by_Tail(list, a[i]);
        }
        print_list(list);
    }
    return 0;
}

2.链表交换

描述

尝试把一个长度为 n 的数组转换成链表并把链表前两个节点交换位置和把链表最后两个节点交换位置。

输入描述

第一行输入一个正整数 n 表示数组的长度
第二行输入 n 个正整数，表示数组中各个元素的值

输出描述

把数组转换成链表后输出交换位置后的链表

示例

  • 输入
    4
    2 3 4 5

  • 输出：
    3 2 5 4

题解

#include <stdio.h>

typedef struct Node
{
    int data;
    struct Node* next;
} Node;

Node* create_list()
{
    Node* head_node = (Node*)malloc(sizeof(Node));
    head_node->next = NULL;
    return head_node;
}

Node* create_node(int data)
{
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

void insert_by_tail(Node* head_node,int data)
{
    Node* new_node = create_node(data);
    Node* test = NULL;
    for(test = head_node;test->next!=NULL;test = test->next);
    test->next = new_node;
}

void print_list(Node* head_node)
{
    Node* ptr = head_node->next;
    while(ptr)
    {
        printf("%d ",ptr->data);
        ptr = ptr->next;
    }
}

void change(Node* head_node)
{
    int tmp1 = 0;
    tmp1 = head_node->next->next->data;
    head_node->next->next->data = head_node->next->data;
    head_node->next->data = tmp1;

    int tmp2 = 0;
    Node* ptrtest = head_node;
    while(ptrtest->next->next)
    {
        ptrtest = ptrtest->next;
    }
    tmp2 = ptrtest->next->data;
    ptrtest->next->data = ptrtest->data;
    ptrtest->data =  tmp2;
}

int main() 
{
    int n;
    int arr[100];
    Node* List = create_list();
    while(scanf("%d",&n)!=EOF)
    {
        for(int i = 0;i < n;i++)
        {
            scanf("%d",&arr[i]);
            insert_by_tail(List,arr[i]);
        }
        change(List);
        print_list(List);
    }

    return 0;
}

3.单链表求和

描述

输入一个长度为 n 的数组，他想把这个数组转换成链表，链表上每个节点的值对应数组中一个元素的值，然后遍历链表并求和各节点的值。

输入描述

第一行输入一个正整数 n ，表示数组的长度。
第二行输入 n 个正整数，表示数组中各个元素的值。

输出描述：

把数组转换成链表然后对其求和并输出这个值。

示例

  • 输入
    5
    5 2 3 1 1
  • 输出
    12

题解

#include <math.h>
#include <stdio.h>

typedef struct Node
{
    int data;
    struct Node* next;
}Node;

Node* create_list()
{
    Node* head_node = (Node*)malloc(sizeof(Node));
    head_node->next = NULL;
    return head_node;
}

Node* create_node(int data)
{
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

void insert_by_tail(Node* head_node,int data)
{
    Node* new_node = create_node(data);
    Node* ptrtest = (Node*)malloc(sizeof(Node));
    for(ptrtest = head_node;ptrtest->next!=NULL;ptrtest=ptrtest->next);
    ptrtest->next = new_node;
}

int main() 
{
    int n;
    int arr[10];
    Node* List = create_list();
    while(scanf("%d",&n)!=EOF)
    {
        for(int i = 0;i < n;i++)
        {
            scanf("%d",&arr[i]);
            insert_by_tail(List, arr[i]);
        }
    }
    int sum = 0;
    Node* ptr = List;
    while(ptr)
    {
        sum = sum + ptr->data;
        ptr = ptr->next;
    }
    printf("%d",sum);
    free(ptr);
    ptr = NULL;
    free(List);
    return 0;
}

4.双链表求和

描述

输入两个长度相同的数组分别是 a 和 b ，然后把数组 a 和 b 转换成链表 a 和链表 b 。把链表 a 中的全部值按顺序加到链表 b 中。

输入描述

第一行输入一个正整数 n ，表示数组的长度。
第二行和第三行分别输入 n 个正整数，表示数组 a 和 数组 b 的值。

输出描述

把数组 a 和数组 b 转换成链表，然后把链表 a 中的值加到链表 b 中，然后输出加和后的链表。

示例

  • 输入
    5
    5 4 2 1 3
    2 4 5 8 9

  • 输出
    7 8 7 9 12

题解

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
    int data;
    struct Node* next;
}Node;

Node* create_list()
{
    Node* head_node = (Node*)malloc(sizeof(Node));
    head_node->next = NULL;
    return head_node;
}

Node* create_new_node(int data)
{
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

void insert_by_tail(Node* head_node,int data)
{
    Node* new_node = create_new_node(data);
    Node* ptr = NULL;
    for(ptr = head_node;ptr->next != NULL;ptr = ptr->next);
    ptr->next = new_node;
}

void list_sum(Node* head_node1,Node* head_node2,int* arr3)
{
    Node* test1 = head_node1->next;
    Node* test2 = head_node2->next;
    int i = 0;
    while(test1 && test2)
    {
        arr3[i] = test1->data + test2->data;
        test1 = test1->next;
        test2 = test2->next;
        i++;
    }
}

int main() 
{
    int n;
    scanf("%d",&n);
    int arr1[n];
    int arr2[n];
    Node* A = create_list();
    Node* B = create_list();
    for(int i = 0;i < n;i++)
    {
        scanf("%d",&arr1[i]);
        insert_by_tail(A, arr1[i]);
    }
    for(int i = 0;i < n;i++)
    {
        scanf("%d",&arr2[i]);
        insert_by_tail(B, arr2[i]);
    }

    int arr3[n];
    Node* C = create_list();
    list_sum(A, B, arr3);

    for (int i = 0;i < n;i++)
    {
        insert_by_tail(C, arr3[i]);
    }
	
	//打印
    Node* printptr = (Node*)malloc(sizeof(Node));
    for(printptr = C->next;printptr!=NULL;printptr = printptr->next)
    {
        printf("%d ",printptr->data);
    }
    return 0;
}

5.链表删除

描述

牛牛从键盘输入了一个长度为 n 的数组，把这个数组转换成链表然后把链表中所有值是 x 的节点都删除。

输入描述

第一行输入两个正整数 n 和 x 表示数组的长度和要删除的链表节点值 x 。
第二行输入 n 个正整数表示数组中每个元素的值。

输出描述

把数组转换成链表然后删除所有值是 x 的节点，删除后输出这个链表。

示例

  • 输入
    5 3
    1 5 3 2 3
  • 输出
    1 5 2

题解

#include <malloc.h>
#include <stdio.h>

typedef struct Node
{
    int data;
    struct Node* next;
}Node;

Node* create_list()
{
    Node* head_node = (Node*)malloc(sizeof(Node));
    head_node->next = NULL;
    return head_node;
}

Node* create_node(int data)
{
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

void insert_by_tail(Node* head_node,int data)
{
    Node* ptr = NULL;
    Node* new_node = create_node(data);
    for(ptr = head_node;ptr->next!=NULL;ptr=ptr->next);
    ptr->next = new_node;
}

void delete(Node* head_node,int x)
{
    Node* test = head_node;
    while(test->next != NULL)
    {
        if(test->next->data == x)
        {
            test->next = test->next->next;
        }
        test = test->next;
    }
}

void print_list(Node* head_node)
{
    Node* printptr = head_node->next;
    while(printptr != NULL)
    {
        printf("%d ",printptr->data);
        printptr = printptr->next;
    }
}

int main() 
{
    int n = 0;
    scanf("%d",&n);
    int x = 0;
    scanf("%d",&x);

    Node* L = create_list();
    int arr[n];
    for (int i = 0;i < n;i++)
    {
        scanf("%d",&arr[i]);
        insert_by_tail(L, arr[i]);
    }
    delete(L, x);
    print_list(L);
    return 0;
}

6.链表添加结点

描述

输入一个长度为 n 的数组，他把这个数组转换成链表并在第 i 个节点的后面添加一个值为 i 的新节点

输入描述

第一行输入两个正整数分别是 n 和 i ，表示数组的长度、需要添加节点的位置和节点的值
第二行输入 n 个正整数表示数组中每个元素的值

输出描述

把数组转换成链表并在第 i 个节点后的添加一个新节点值，新节点的值是 i

示例

  • 输入
    5 3
    5 4 8 6 3

  • 输出
    5 4 8 3 6 3

题解

#include <stdio.h>
#include <string.h>

typedef struct Node
{
    int data;
    struct Node* next;
}Node;

Node* create_list()
{
    Node* head_node = (Node*)malloc(sizeof(Node));
    head_node->next = NULL;
    return head_node;
}

Node* create_new_node(int data)
{
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

void insert_by_tail(Node* head_node,int data)
{  
    Node* new_node = create_new_node(data);
    Node* ptr = NULL;
    for(ptr = head_node;ptr->next!=NULL;ptr = ptr->next);
    ptr->next = new_node;
}

void print_list(Node* head_node)
{
    Node* test = head_node->next;
    while(test)
    {
        printf("%d ",test->data);
        test = test->next;
    }
}

void insert(Node* head_node,int i)
{
    Node* in_node = create_new_node(i);
    Node* inptr = head_node;
    while(i)
    {
        inptr = inptr->next;
        i--;
    }
    in_node->next = inptr->next;
    inptr->next = in_node;
}

int main() 
{
    int n = 0;
    scanf("%d",&n);
    int arr[n];
    int i = 0;
    scanf("%d",&i);
    Node* L = create_list();
    for(int j = 0;j < n;j++)
    {
         scanf("%d",&arr[i]);
         insert_by_tail(L,arr[i]);
    }

    insert(L, i);
    print_list(L);
    return 0;
}

7.反转链表

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

NowCoder

链表题解

C语言 | NowCoder链表题解 的相关文章

  • 51单片机（ESP8266模块）

    前言 xff1a 蓝牙 xff0c ESP 01s xff0c Zigbee NB Iot等通信模块都是基于AT指令的设计 一 AT指令 AT指令集是从终端设备 xff08 Terminal Equipment xff0c TE 或数据终端

  • 嵌入式工作机会会越来越少吗

    我认为嵌入式工作会越来越多 在当前产业结构升级的大背景下 xff0c 物联网会与诸多的行业领域产生更加紧密的联系 xff0c 而这个过程必然离不开嵌入式开发的参与 应用场景对于嵌入式开发领域的发展有非常直接的影响 xff0c 嵌入式开发要想

  • 大学生为何很想往嵌入式方向发展？

    这几年嵌入式工资一直在再涨 xff0c 挺好的 xff01 可以选择的公司也比较多 xff0c 起薪差不读在10k 13k的样子 招聘公司统计的数据是19K 优点1 xff1a 应届生嵌入式行业的薪资在毕业生眼里看来真的是很香 xff0c

  • 涨姿势 | 一文说透电机控制器硬件在环测试（MCU HIL）

    软件质量是嵌入式产品开发中最关注的问题之一 随着产品迭代 xff0c 软件复杂程度越来越高 xff0c 为保证软件质量 xff0c 需要对软件进行大量的测试 xff0c 这会在整个产品周期中消耗大量时间及资源 另一方面 xff0c 市场竞争

  • VMware Workstation创建Windows 11（21H2）虚拟机

    2021年6月24日 xff0c 微软发布了Windows 11 xff0c 很多人都想 尝尝鲜 可以为较高的电脑配置 xff0c 使得很多老电脑 望而却步 xff0c 或者有人想换可又嫌麻烦或不舍得 所以今天我来带大家创建Windows

  • 计算机知识——常见的存储类型

    一 常见存储器类型 xff1a 1 易失 非易失性存储器 xff1a 是指存储器断电后 xff0c 它存储的数据内容是否会丢失的特性 由于一般易失性存储器存取速度快 xff0c 而非易失性存储器可长期保存数据 易失性存储器最典型的代表是内存

  • 使用select函数实现TCP并发服务器

    首先介绍一下select 函数的功能 参数 返回值 int select int nfds fd set readfds fd set writefds fd set exceptfds struct timeval timeout voi

  • ROS下gazebo打不开，最新最全的可行方法

    问题具体描述 xff1a 在打开roscore的情况下 执行命令行 xff1a rosrun gazebo ros gazebo 或者命令行 xff1a roslaunch gazebo ros empty world launch 但是只

  • 西门子S7-200SMART模拟量输入、输出模块接线

    西门子S7 200SMART模拟量输入 输出模块接线 https www bilibili com video BV1J3411R7nu spm id from 61 333 337 search card all click 西门子S7

  • SyntaxError: Non-ASCII character ‘\xe9‘报错

    本人在用vscode写python代码时 xff0c 第一次运行就遇到了这种情况 解决方法 xff1a 在python文件开头加上以下一行 xff1a coding utf 8 如下图所示 xff1a 即可解决报错问题 xff08 注意 x

  • 最新：ubuntu18.04下，vscode报错：No such file or directory

    我遇到的问题是 xff1a 在vscode编译下是没有报错的 xff0c 但是运行文件时 xff0c 还是报错了 如下图所示 xff1a 实际上 xff0c vscode会经常遇到这种类似的问题 xff0c 建议可以使用ubuntu的终端运

  • 打开了ros中的rviz，显示不了机器人模型

    问题 xff1a 可以打开gazebo xff0c 但是打开rviz后 xff0c 显示不了机器人模型 报错情况如下图所示 xff1a 解决 xff1a 看看自己的launch文件是否加了以下的节点 xff1a lt node pkg 61

随机推荐

热门标签