往年EMC编程题答案

1 Write a function to find the Kth node form the last node of a singly-linked list, and analze the time and space complexity of your funciton.
The input to the function is a pointer or reference to the head of the list.
The output is a pointer or reference to the Kth node from the last node.

?

用两个指针p, ? q同时指向第一个节点, ? q先向前走n步, ? 然后p, ? q同时前进, ? 当q走到最后一个节点时, ? p即指向倒数第n个.


typedef ? struct
{
? ? ? ? int ? i;
? ? ? ? Node ? *next;
}Node;

Node ? *test(Node ? *t,int ? n)
{

? ? ? ? Node ? *p, ? *q;

? ? ? ? p ? = ? t;
? ? ? ? q ? = ? t;

? ? ? ? while(n-- ? > ? 0) ? //没有考虑接点个数小于n的情况 ?
? ? ? ? ? ? ? ? q ? = ? q-> next;

? ? ? ? while(q ? != ? NULL)
? ? ? ? {
? ? ? ? ? ? ? ? p ? = ? p-> next;
? ? ? ? ? ? ? ? q ? = ? q-> next;
? ? ? ? }

? ? ? ? return ? p;
}

?

2

写一个函数找出一个整数数组中，第二大的数#include <stdio.h>const int MINNUMBER = -32767int find_sec_max(int data[], int count){     int maxnumber = data[0];     int sec_max = MINNUMBER;     int i = 0;           for(i = 1; i < count; i++){             if(data[i] > maxnuber){                    sec_max = maxnumber;                    maxnumber = data[i]:             }             else if(data[i] > sec_max){                     sec_max = data[i];              }        }        return sec_max;}?