当前位置：首页 > news >正文

猿创征文｜【数据结构】牛客网刷题

news 来源：原创 2024/5/4 5:58:33

💬推荐一款模拟面试、刷题神器、从基础到大厂面试题：👉点击跳转刷题网站进行注册学习

一、牛牛的单向链表

二、牛牛的链表交换

三、牛牛的单链表求和

一、牛牛的单向链表

先设定一个新的结点名用于存储新结点中包含的信息。
设定一个新结构体访问头结点的位置，这个位置信息是由创建结点函数的返回值确定的。（链表开始的地方，不变，每次访问都是0x0）。
从头结点开始遍历，判断是否为最后一个结点。（标志：最后一个结点的下一个结点指向NULL。）
- 如果不是，则把结点首地址赋为该结点的下一个结点。
- 再重新访问，直到最后一个结点。（此处需要一个while循环）
到最后一个结点，它的下一个结点指向NULL，跳出循环，把新收到的结点赋给把最后一个结点，完成插入。
结束后加一个count++可以用于计算链表长度或者尾插次数。

本题需要注意的是尾插函数的返回值，这个是由题目之中的输出要求得到的。

#include <stdio.h>
typedef struct Lnode{
    int data;
    struct Lnode *next;
}Lnode;
int main(){
    int n, temp;
    scanf("%d",&n);
    //头节点
    Lnode *L = (Lnode *)malloc(sizeof(Lnode));
    //r尾指针，用来连接尾节点和新建节点
    Lnode *s,*r= L;
    //建表
    while(n--){
        scanf("%d",&temp);
        s = (Lnode *)malloc(sizeof(Lnode));
        s->data = temp;
        r->next = s;
        r = s;
    }
    r->next = NULL;
    //遍历输出节点值
    while(L->next != NULL){
        L = L->next;
        printf("%d ",L->data);
    }
    return 0;
}

二、牛牛的链表交换

本题可以考虑先对数组前两个元素和后两个元素进行交换，再将数据拷贝整合至链表会方便很多。

#include<stdio.h>
#include<stdlib.h>
struct Node{
    int data;
    struct Node* next;
};
void swap(struct Node* HeadNode,int n){
    int i;
    HeadNode=HeadNode->next;
    int flag;
    for(i=0;i<n;i++){
        if(i==0){
            flag=HeadNode->data;
            HeadNode->data=HeadNode->next->data;
            HeadNode->next->data=flag;
            i++;
        }
        if(i==n-1){
            flag=HeadNode->data;
            HeadNode->data=HeadNode->next->data;
            HeadNode->next->data=flag;
        }
        HeadNode=HeadNode->next;
    }

}
void Print(struct Node* HeadNode){
    HeadNode=HeadNode->next;
    while(HeadNode->next!=NULL){
        printf("%d ",HeadNode->data);
        HeadNode=HeadNode->next;
    }
    printf("%d",HeadNode->data);
}
int main(){
    int n;
    scanf("%d",&n);
    int i;
    int num;
    struct Node* HeadNode=(struct Node*)malloc(sizeof(struct Node));
    struct Node* PosNode=(struct Node*)malloc(sizeof(struct Node));
    HeadNode->next=NULL;
    PosNode=HeadNode;
    for(i=0;i<n;i++){
        struct Node* newNode=(struct Node*)malloc(sizeof(struct Node));
        scanf("%d",&num);
        newNode->data=num;
        newNode->next=NULL;
        PosNode->next=newNode;
        PosNode=newNode;
    }
    swap(HeadNode,n);
    Print(HeadNode);
}