pta——递增的整数序列链表的插入，奇数值结点链表

6-8 递增的整数序列链表的插入

本题要求实现一个函数，在递增的整数序列链表（带头结点）中插入一个新整数，并保持该序列的有序性。

函数接口定义：

List Insert( List L, ElementType X );
1

其中结构定义如下：List

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */
1
2
3
4
5
6

L是给定的带头结点的单链表，其结点存储的数据是递增有序的； 函数要将插入，并保持该序列的有序性，返回插入后的链表头指针。InsertXL

裁判测试程序样例：

#include 
#include 

typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
    ElementType Data;
    PtrToNode   Next;
};
typedef PtrToNode List;

List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表 */

List Insert( List L, ElementType X );

整型主()
{
    List L;
    ElementType X;
    L = Read();
    scanf("%d", &X);
    L = Insert(L, X);
    Print(L);
    return 0;
}

/* 你的代码将被嵌在这里 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

输入样例：
5
1 2 4 5 6
3
输出样例：
1 2 3 4 5 6
第一次写的，也没有啥循环套循环的就超时了

List Insert(List L,ElementType X)
{
	List p,q,c;
	p = L;
	c = (struct Node*)malloc(sizeof(struct Node));
	c->Data = X;
	c->Next = NULL;
	//如果X插在链表头
	if(X<p->Data){
		c->Next = p->Next;
		p->Next = L;
		return L; 
	}
	while(p->Next!=NULL){
		q = p->Next;
		if(X>p->Data&&X<q->Data){
	    	c->Next = q;
			p->Next = c;
			return L;
		}
		p = q;
	}
	//比到空了X直接插在链表尾
	p->Next = c;
	return L;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

好像自己考虑的还挺周到其实是自己愚笨了。

List Insert(List L,ElementType X)
{
	List p,c;
	p = L;
	c = (struct Node*)malloc(sizeof(struct Node));
	c->Data = X;
	c->Next = NULL;
	while(p->Next!=NULL&&X>p->Next->Data){
        p = p->Next;
	}
	c->Next = p->Next;
	p->Next = c;
	return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

6-4 奇数值结点链表

本题要求实现两个函数，分别将读入的数据存储为单链表、将链表中奇数值的结点重新组成一个新的链表。 链表结点定义如下：

struct ListNode {
    int data;
    ListNode *next;
};
1
2
3
4

函数接口定义：

struct ListNode *readlist();
struct ListNode *getodd( struct ListNode **L );
1
2

函数从标准输入读入一系列正整数，按照读入顺序建立单链表。 当读到readlist−1时表示输入结束，函数应返回指向单链表头结点的指针。

函数将单链表中奇数值的结点分离出来，重新组成一个新的链表。 返回指向新链表头结点的指针，同时将中存储的地址改为删除了奇数值结点后的链表的头结点地址（所以要传入的指针）。getoddLLL

裁判测试程序样例：

#include 
#include 

struct ListNode {
    int data;
    struct ListNode *next;
};

struct ListNode *readlist();
struct ListNode *getodd( struct ListNode **L );
void printlist( struct ListNode *L )
{
     struct ListNode *p = L;
     while (p) {
           printf("%d ", p->data);
           p = p->next;
     }
     printf("\n");
}

int main()
{
    struct ListNode *L, *Odd;
    L = readlist();
    Odd = getodd(&L);
    printlist(Odd);
    printlist(L);

    return 0;
}

/* 你的代码将被嵌在这里 */

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

输入样例：
1 2 2 3 4 5 6 7 -1
输出样例：
1 3 5 7
2 2 4 6

struct ListNode *readlist()
{
	struct ListNode *p,*head,*last;
	p = (struct ListNode*)malloc(sizeof(struct ListNode));
	p->next = NULL;
	last = NULL;
	scanf("%d",&p->data );
	head = p;
	while(p->data != -1){
		last = p;
		p = (struct ListNode*)malloc(sizeof(struct ListNode));
		scanf("%d",&p->data );
        last->next = p;
	}
	last->next = NULL;
	return head;
}
struct ListNode *getodd( struct ListNode **L )
{
	struct ListNode *p,*last,*head,*pp;
	p = *L;
	head = NULL;
	pp = head;
	last = p;
	for(;p;p=p->next ){
		if(p->data %2==1){
			if(head == NULL){
				head = p;
				pp = head;
			}
			else{
				pp->next = p;
				pp = p;
			}
			//如果是奇数还在要原链表里删除它
			if(p==*L){
				*L = p->next ;
				last = p->next ;
			}
			else{
				last->next = p->next ; 
			}
		}
		else{
			last = p;
		}
	}
	if(pp){
		pp->next = NULL;
	}
	return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52