面试题集锦_7

将单向链表reverse，如ABCD变成DCBA，只能搜索链表一次。
 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 typedef struct LNode{
 4 int data;
 5 struct LNode *next;
 6 }LNode,*LinkList;
 7 void CreateList_L(LinkList &L,int n)
 8 {
 9     L=(LinkList)malloc(sizeof(LNode));
10     L->next=NULL;//头结点
11     LinkList p,q;
12     p=L;
13     //p=p->next;
14     for(int i=0;i<n;i++)
15     {
16         q=(LinkList)malloc(sizeof(LNode));
17         p->next=q;
18         //scanf("%d",&q->data);//在用“％c”格式输入字符时，空格字符和“转义字符”都作为有效字符输入
19         scanf("%c",&q->data);
20         //q->data=getchar();
21         q->next=NULL;
22         p=q;//这下知道前驱指针的作用，只是还有些不明白为什么那样就会出错
23     }//顺序建立单链表
24     printf("链表创建成功！\n");
25 }
26 void Reverse(LinkList &L,int n)
27 {
28     LinkList q=L,qt;
29     q=q->next;
30     for(int i=0;i<n;i++)
31     {
32         qt=(LinkList)malloc(sizeof(LNode));
33         qt->data=q->data;
34         q=q->next;
35         qt->next=L->next;
36         L->next=qt;
37     }
38     printf("逆序成功！\n");
39 }
40 void Display(LinkList L)
41 {
42    L=L->next;
43    while(L!=NULL)
44    {
45        printf("%c",L->data);
46        L=L->next;
47    }
48 }
49 int main()
50 {
51     LinkList L;
52     int n;
53     printf("输入你要创建的链表的大小:\n");
54     scanf("%d",&n);
55     CreateList_L(L,n);
56     Display(L);
57     Reverse(L,n);
58     Display(L);
59 }
View Code
没有删除后面结点，现在不适合想，先存。