关于数据结构和算法:PIPIOJ1267-删除单链表的倒数第K个节点

87次阅读

共计 1086 个字符,预计需要花费 3 分钟才能阅读完成。

题目形容

给定一个长度为 n 的单链表,删除倒数第 K 的节点,而后从头到尾输入每个节点的值。

输出

第一行蕴含两个整数 N,k,k<=N.
第二行蕴含 N 个整数,代表从表头到表尾每个节点的值。
你须要建设单链表把这 N 个数串起来~

输入

按程序输入删除了倒数第 K 个节点后每个节点的值。

样例输出

5 2
1 2 3 4 5

样例输入

1 2 3 5

C++ 参考解答

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

typedef int ElemType;

typedef struct LNode {
    ElemType data;
    struct LNode* next;
}LNode,*LinkList;

// 尾插法创立单链表
LinkList CreateList(LinkList& L,int N) {L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    LNode* s, *r = L;
    int i = 0,x;
    while (i < N) {scanf("%d", &x);
        s = (LinkList)malloc(sizeof(LNode));
        s->data = x;
        s->next = r->next;
        r->next = s;
        r = s;
        i++;
    }
    r->next = NULL;
    return L;
}

// 输入单链表
void PrintList(LinkList L) {
    LNode* s = L->next;
    while (s) {printf("%d", s->data);
        s = s->next;
    }
    printf("\n");
}

// 按值查找
LinkList GetElem(LinkList L,int i) {
    int j = 1;
    LNode* p = L->next;
    if (i == 0) {return  L;}
    if (i < 1) {return NULL;}
    while (p && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

// 删除单链表中第 i 个结点
bool ListDelete(LinkList& L, int i) {LNode* p = GetElem(L, i - 1);
    if (p == NULL) {return false;}
    LNode* q = p->next;
    if (q == NULL) {return false;}
    p->next = q->next;
    free(q);
    q = NULL;
    return true;
}

int main() {
    int N, k;
    scanf("%d%d", &N, &k);
    int seqloc = N - k+1;
    LinkList L;
    CreateList(L,N);
    ListDelete(L, seqloc);
    PrintList(L);
    return 0;
}

正文完
 0