有关链表的题解

7-1单链表基本操作

题目描述

请���写程序实现单链表插入、删除结点等基本算法。给定一个单链表和一系列插入、删除结点的操作序列，输出实施上述操作后的链表。单链表数据域值为整数。

输入格式

输入第1行为1个正整数n，表示当前单链表长度；第2行为n个空格间隔的整数，为该链表n个元素的数据域值。第3行为1个正整数m，表示对该链表施加的操作数量；接下来m行，每行表示一个操作，为2个或3个整数，格式为0 k d或1 k。0 k d表示在链表第k个结点后插入一个数据域值为d的结点，若k=0则表示表头插入。1 k表示删除链表中第k个结点，此时k不能为0。注：操作序列中若含有不合法的操作（如在长度为5的链表中删除第8个结点、删除第0个结点等），则忽略该操作。n和m不超过100000。

输出格式

输出为一行整数，表示实施上述m个操作后的链表，每个整数后一个空格。输入数据保证结果链表不空。

输入样例

51 2 3 4 550 2 80 9 60 0 71 0 1 6

输出样例

7 1 2 8 3 5 

题目分析

本题是一道基础的单链表题目，考察单链表的创建、头插节点、在指定节点后插入节点、删除指定节点。

通过输入格式可知有一个操作符我们设为flag：当flag为0时又分为两种情况（k为0时为头插，k不为0且合法时为在k后插入新节点）；当flag为1时则为删除指定位置节点。

注意： 当k的值不属于该链表的节点时（大于链表长度或者小于0）就忽略这个操作。

代码实现

#include#include//链表基本节点单位typedef struct SListNode {    int num;    struct SListNode* next;}SLTNode;//创建节点SLTNode* CreatNewNode(int x) {    SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));//开辟空间    newNode->num = x;    newNode->next = NULL;//新节点的下一节点指向空    return newNode;}//打印链表，phead为头节点void ListPrint(SLTNode* phead) {    SLTNode* pcur = phead;    while (pcur) {//pcur遍历链表直到为空结束循环        printf("%d ", pcur->num);        pcur = pcur->next;    }}//插入节点，pphead为指向头结点（phead）的地址void PushBack(SLTNode** pphead, int k, int x) {    SLTNode* newnode = CreatNewNode(x);//先调用上面的函数创建新节点    if (*pphead == NULL) {//当phead为空时，新建节点为头结点        *pphead = newnode;        return;    }    if (k == 0) {//k为0时头插节点         newnode->next = *pphead;        *pphead = newnode;    }    else{        SLTNode* prev = *pphead;//prev遍历链表        int i = 1;//i为遍历节点数量        while (prev->next) {            if (i == k) {//当到达指定位置在该节点后插入新节点                newnode->next = prev->next;//新节点下一节点指向当前节点的下一节点                break;            }            prev = prev->next;//未达到指定节点继续遍历            i++;        }        prev->next = newnode;//当前节点指向新节点完成插入    }}//删除节点void delDigit(SLTNode** pphead, int k) {    SLTNode* prev = *pphead;//prev遍历链表    int i = 1;    while (prev->next ) {        if (i == k-1) {        SLTNode* now=prev->next;//now指向要删除的节点            prev->next = now->next;//跳过要删除的节点重新链接链表            free(now);//释放要删除链表            return;        }        prev = prev->next;//不断遍历        i++;    }}int main(){    int m, n;//n为节点数，m为操作次数    scanf("%d", &n);    //创建初始链表    SLTNode* plist = NULL;    for (int i = 1; i         int x; scanf("%d", &x);        PushBack(&plist, i, x);    }    //执行操作步骤    scanf("%d", &m);    while (m--) {        int flag; scanf("%d", &flag);//flag操作符        if (flag == 0) {            int k, d; scanf("%d %d", &k, &d);            if (k  n || k  n || k     int x;    list* next;};int main(){    int n, m;    cin > n >> m;//输入节点数和出局数    list* phead, * ptail, * now, * prev;     //创建环链表    phead = new list;//先创建头结点（c++中new可以看做c中malloc）    phead->x = 1;//第一个节点为1    phead->next = NULL;    now = phead;//now遍历节点    for (int i = 2; i         ptail = new list;//ptail不断创造尾节点        ptail-x = i;        ptail->next = NULL;        now->next = ptail;//通过now->next使链表连接起来        now = ptail;    }    now->next = phead;//通过最后一个节点指向头结点来实现链表循环    now = phead;    prev = phead;    //下面开始遍历，当剩余节点数为1时结束    while (n!=1)    {        for (int i = 1; i next;        }        prev->next = now->next;        now = prev->next;        n--;//删除一个节点    }    cout x;//打印剩余节点    delete now;//清空链表}

C代码实现

#include#includetypedef struct ListNode {    int num;    struct ListNode* next;}ListNode;//创建节点ListNode* CreateNode(int x) {    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));    newNode->num = x;    newNode->next = NULL;    return newNode;}//创建链表ListNode* CreateList(int n) {    ListNode* phead = CreateNode(1);    ListNode* ptail = phead;    for (int i = 2; i //链表赋值        ptail-next = CreateNode(i);//创建一个新节点        ptail = ptail->next;//ptail指向创建的新节点    }    ptail->next = phead;//使单链表链接起来形成环    return phead;}//约瑟夫环主要流程void ysf(int n, int m) {    ListNode* phead = CreateList(n);//创建由n个节点组成的环链表    ListNode* pcur = phead;//遍历链表    ListNode* prev = phead;    n--;    while (n--) {        for (int i = 1; i next;        }        prev->next = pcur->next;        pcur = prev->next;    }    printf("%d", pcur->num);    //free(phead);}int main(){    int n, m;    scanf("%d %d", &n, &m);    ysf(n, m);    return 0;}

图片分析