数据结构链表相关问题

Question

1.某单链表中的数据元素结构如下：

struct node{

    char data；

    struct node * next；

}

并有如下别名：

typedef struct node * linklist；

要求实现一个函数，打印链表中的倒数第k个结点中的值（如果有的话），并返回0；如果找不到，则返回-1 。函数原型如下：

int print_k(linklist l，int k)

1. 定义一个定长整型数组结构（结构体类型），设计两个算法：①.在第一次出现的元素y之前插入元素x；②.将所有奇数元素放在前面、偶数元素放在后面，并说明这两个算法的时间、空间复杂度。

Answer 1

问题1：

int print_k(linklist l，int k)
{
int * arr = (int *)malloc(sizeof(int) * k);
for (int i = 0; i < k; i++) arr[i] = -1;
while (l)
{
for (int i = 1; i < k; i++) arr[i] = arr[i - 1];
arr[0] = l->data;
l = l->next;
}
return arr[0];
}

问题2：

#include <stdio.h>
#include <stdlib.h>
typeof struct 
{
int N;
int *arr;
} * Sqlist;
int main()
{
int N;
scanf("%d", &N);
Sqlist; l;
l->N = N + 1; 
l->arr = (int *) malloc(sizeof(int) * (N + 1)) ;
for (int i = 0; i < N; i++) scanf("%d", &l->arr[i]);
int y;
int x;
scanf("%d%d",&x, &y);
int j = 0;
for (j = 0; j < N; j++) if (l->arr[i] == y) break;
for (int k = N; k > i; k--) l->arr[k] = l->arr[k - 1]; 
arr[j] = x;
}

算法时间复杂度O(n)，空间复杂度O(1)