面试之单链表

1、编程实现一个单链表的建立/测长/打印。

       答案：

?

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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70

#include<iostream> using namespace std;   //单链表结构体 typedef struct student {     int data;     struct student *next; }node;   //建立单链表 node *create() {     node *head,*p,*s;     int x,cycle=1;     head=(node*)malloc(sizeof(node)); //建立头节点     p=head;     while(cycle)     {         printf("\nPlease input the data:");         scanf("%d",&x);         if(x!=0)         {             s=(node*)malloc(sizeof(node));//每次新建一个节点             s->data=x;             printf("\n%d",s->data);             p->next=s;             p=s;         }         else         {             cycle=0;         }     }     head=head->next;     p->next=NULL;     printf("\n   yyy   %d",head->data);     return (head); }   //单链表测长 int length(node *head) {     int n=0;     node *p;     p=head;     while(p!=NULL)     {         p=p->next;         n++;     }     return (n); }   //单链表打印 void print(node *head) {     node *p;     int n;     n=length(head);     printf("\nNow,These %d records are :\n",n);     p=head;     if(head!=NULL)         p=p->next;     while(p!=NULL)     {         printf("\n   uuu  %d    ",p->data);         p=p->next;     } }

 

2、编程实现单链表删除节点。

      解析：如果删除的是头节点，如下图：

 

     则把head指针指向头节点的下一个节点。同时free p1，如下图所示：

 

    如果删除的是中间节点，如下图所示：

 

    则用p2的next指向p1的next同时，free p1 ，如下图所示：

 

答案：

?

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

//单链表删除节点 node *remove(node *head ,int num) {     node *p1,*p2;     p1=head;     while(num!=p1->data && p1->next!=NULL)//查找data为num的节点     {         p2=p1;         p1=p1->next;     }     if(num==p1->data) //如果存在num节点，则删除     {         if(p1==head)         {             head=p1->next;             free(p1);         }         else         {             p2->next=p1->next;         }     }     else     {         printf("\n%d could not been found",num);     }     return (head); }

 

3、编写程序实现单链表的插入。

      解析：单链表的插入，如下图所示：

 

     如果插入在头结点以前，则p0的next指向p1，头节点指向p0，如下图所示：

 

    如果插入中间节点，如下图所示：

 

    则先让p2的next指向p0，再让p0指向p1，如下图所示：

 

    如果插入尾节点，如下图所示：

 

    则先让p1的next指向p0，再让p0指向空，如下图所示：

 

   答案：

?

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

//单链表插入节点 node *insert(node *head,int num) {     node *p0,*p1,*p2;     p1=head;     p0=(node *)malloc(sizeof(node));     p0->data=num;     while(p0->data > p1->data && p1->next!=NULL)     {         p2==p1;         p1=p1->next;     }     if(p0->data<=p1->data)     {         if(head==p1)         {             p0->next=p1;             head=p0;         }         else         {             p2->next=p0;             p0->next=p1;         }     }     else     {         p1->next=p0;         p0->next=NULL;     }     return (head); }

 

4、编程实现单链表的排序。

     答案：

?

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

//单链表排序 node *sort(node *head) {     node *p,*p2,*p3;     int n;     int temp;     n=length(head);     if(head==NULL ||head->next==NULL)//如果只有一个或者没有节点         return head;     p=head;     for(int j=1;j<n;++j)     {         p=head;         for(int i=0;i<n-j;++i)         {             if(p->data > p->next->data)             {                 temp=p->data;                 p->data=p->next->data;                 p->next->data=temp;             }             p=p->next;         }     }     return (head); }

 

5、编写实现单链表的逆置。

     解析：单链表模型如下图所示：

 

    进行单链表逆置，首先要让p2的next指向p1，如下图所示：

 

    再由p1指向p2，p2指向p3，如下图所示：

 

    让后重复p2的next指向p1，p1指向p2，p2指向p3。

 

   答案：

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

//单链表逆置 node *reverse(node *head) {     node *p1,*p2,*p3;     if(head==NULL || head->next==NULL)         return head;     p1=head;     p2=p1->next;     while(p2)     {         p3=p2->next;         p2->next=p1;         p1=p2;         p2=p3;     }     head->next=NULL;     head=p1;     return head; }

 

6、编程实现删除单链表的头元素。

    答案：

?

1 2 3 4 5 6 7 8

//删除单链表的头元素 void RemoveHead(node *head) {     node *p;     p=head;     head=head->next;     free(p); }

 

7、给出一个单链表，不知道节点N的值，怎么只遍历一次就可以求出中间节点，写出算法。

    解析：设立两个指针，比如*p和*q。p每次移动两个位置，即p=p->next->next，q每次移动一个位置，即q=q->next。当p达到最后一个节点时，q就是中间节点了。

    答案：

 

?

1 2 3 4 5 6 7 8 9 10 11 12 13

//给出一个单链表，不知道节点N的值，怎么只遍历一次就可以求出中间节点 void searchmid(node *head,node *mid) {     node *p,*q;     p=head;     q=head;     while(p->next->next!=NULL)     {         p=p->next->next;         q=q->next;         mid=q;     } }

 

 

8、给定一个单向链表，设计一个时间优化并且空间优化的算法，找出该链表的倒数第m个元素。实现您的算法，注意处理相关的出错情况。m定义为当m=0时，返回链表最后一个元素。

    解析：这是一个难题，我们需要的是倒数第m个元素，所以如果我们从某个元素开始，遍历了m个元素之后刚好到达链表末尾，那么这个元素就是要找的元素。也许从链表的尾部倒推回去不是最好的办法，那么我们可以从链表头开始计数。

    思路一：我们可以先一次遍历求出链表的总长度n，然后顺序变量求出第n-m个元素，那么这个就是我们要找的元素了。

    思路二：我们用两个指针，一个当前位置指针p和一个指向第m个元素的指针q，需要确保两个指针之间相差m个元素，然后以同样的速度移动它们，如果当q到达链表末尾时，那么p指针就是指向倒数第m个元素了。

    答案：

?

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

//思路一 node *searchLastElement1(node *head,int m) {     if(head==NULL)         return NULL;     node *p=head;     int count=0;     while(p!=NULL)     {         p=p->next;         count++;     }       if(count<m)         return NULL;       p=head;     for(int i=0;i<count-m;i++)     {         p=p->next;     }     return p; }   //思路二 node *searchLastElement2(node *head,int m) {     if(head==NULL)         return NULL;     node *p,*q;     p=head;     for(int i=0;i<m;i++)     {         if(p->next!=NULL)         {             p=p->next;         }         else         {             return NULL;         }     }       q=head;     while(p->next!=NULL)     {         p=p->next;         q->next;     }     return q; }