【C++面试题】之单链表

来自：it笨笨 - 博客园

链接：http://www.cnblogs.com/iuices/archive/2011/11/06/2238606.html （点击尾部阅读原文前往）

介绍C++面试题中重要的板块——数据结构，先来看单链表。

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

答案：

#includeusing 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 ，如下图所示：

答案：

//单链表删除节点
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指向空，如下图所示：

答案：

//单链表插入节点
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->datadata)
    {        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、编程实现单链表的排序。

//单链表排序
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;jfor(int i=0;iif(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。

答案：

//单链表逆置
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、编程实现删除单链表的头元素。

答案：

//删除单链表的头元素
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就是中间节点了。

答案： //给出一个单链表，不知道节点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个元素了。

答案：

//思路一
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