`
蒙面考拉
  • 浏览: 160578 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

面试之单链表

 
阅读更多

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、编程实现单链表删除节点。

      解析:如果删除的是头节点,如下图:

QQ截图20111106194807

 

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

QQ截图20111106194959

 

    如果删除的是中间节点,如下图所示:

QQ截图20111106195116

 

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

QQ截图20111106195254

 

答案:

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、编写程序实现单链表的插入。

      解析:单链表的插入,如下图所示:

QQ截图20111106201812

 

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

QQ截图20111106202019

 

    如果插入中间节点,如下图所示:

QQ截图20111106202158

 

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

QQ截图20111106202318

 

    如果插入尾节点,如下图所示:

QQ截图20111106202516

 

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

QQ截图20111106202635

 

   答案:

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,如下图所示:

QQ截图20111106213740

 

    再由p1指向p2,p2指向p3,如下图所示:

QQ截图20111106213748

 

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

QQ截图20111106213759

 

   答案:

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;
}

 

 

分享到:
评论

相关推荐

    单链表的基本操作面试题

    在面试中,对单链表的基本操作是衡量开发者对数据结构理解和编程能力的重要指标。以下是关于单链表建立、查找、插入、删除及特殊操作——检查环、找中间元素和反转的详细知识点。 1. **建立单链表**: 建立单链表...

    面试单链表问题总结-反转,逆序输出,判环,求交点

    这里我们深入探讨一下"面试单链表问题总结-反转,逆序输出,判环,求交点"这四个核心知识点。 首先,**单链表反转**是一个常见的面试题。单链表的基本结构由节点组成,每个节点包含数据和指向下一个节点的指针。...

    单链表基本操作-面试必备

    ### 单链表基本操作-面试必备 #### 知识点概述 单链表是数据结构中的一个重要概念,尤其在编程面试中极为常见。本文将详细介绍单链表的基本操作及其在C语言中的实现方法,包括创建、遍历、释放、计数、查找以及...

    算法大全面试题数据结构单链表的13道面试题含代码

    本篇将详细探讨单链表相关的13道面试题,涵盖其基本操作、查找、反转等重要知识点。 1. **单链表反转**:单链表反转是一项常见的算法题目,主要考察对链表节点操作的理解。通过改变节点间的指向关系,将原链表的...

    C语言 数据结构之单链表基本操作

    单链表的各种操作,适合于初学,也适合于复习 单链表操作介绍 1. 创建头节点 ...12. 面试中常见:单链表翻转 13. 已知两个链表head1和head2各自有序,请把它们合并成一个链表依然有序,要求用递归方法

    【经典面试题】单链表的常见面试题

    文章目录求单链表中有效节点的个数查找单链表中倒数第k个节点【新浪面试题】单链表的反转【腾讯面试题】从尾到头打印单链表【百度面试题,要求方式1:反向遍历。方式2:Stack栈】 单链表的常见面试题有如下: 1.求...

    c++,面试题答案,单链表实现倒叙,

    面试中,特别是针对初级到中级的C++开发者,单链表的逆序操作是一个常见的问题,因为它考察了对数据结构的理解、指针操作以及算法设计的能力。本篇将深入探讨如何用C++实现单链表的倒序。 首先,让我们定义一个...

    JavaScript数据结构之单链表和循环链表

    此外,掌握链表还有助于在面试中展示我们的编程能力和解决问题的能力。 最后,单链表和循环链表的实现及应用是数据结构中的重要内容,也是每一位计算机科学与技术专业学生必须掌握的基础知识。对于在校学生来说,这...

    单链表常考算法及代码

    本文将对单链表的一些常见面试算法进行总结,并提供具体的C++实现代码。 #### 二、知识点概述 1. **创建单链表 (creat_list)** 2. **打印单链表 (print_list)** 3. **计算单链表长度 (list_length)** 4. **删除指定...

    无头节点的单链表

    许多C语言基础面试题都涉及单链表的实现和构造,其目的就是考察面试者对C语言基础数据类型是否有足够的了解,对C语言指针是否掌握。链表的实现可以简单也可以很复杂,只是我们对待问题的态度不同,回想起了大学刚...

    单链表所有操作(C++源码)

    该文件包括单链表的所有操作的C++源代码。 比如: 单链表的创建;单链表的长度;单链表的打印;单链表的删除结点;单链表的插入;单链表的排序;单链表的逆置;求单链表的中结点。 希望对数据结构爱好者有帮助。

    单链表的创建于逆转

    单链表是一种基础的数据结构,...而逆转链表是一个经典的算法问题,经常出现在面试和编程竞赛中,对提高解决问题的能力非常有帮助。在实际项目中,单链表也被广泛应用于各种场景,例如在实现队列、栈或者自定义容器时。

    简单的单链表逆序 非递归

    在计算机科学领域,数据结构是组织、管理和存储数据的有效方式之一,它使数据访问和修改更为高效。其中,链表是一种常见的线性数据结构,由一系列节点组成,每个节点包含数据元素和指向下一个节点的链接。单链表是非...

    单链表之头部插入节点.pdf

    在单链表中,头部插入节点是常见的操作之一,尤其在面试和笔试中常被用来考察对数据结构的理解和编程能力。 首先,我们要了解头插入节点的基本思想。在单链表的头部插入一个新节点意味着新节点将成为链表的第一个...

    单链表反转 链表相交

    实现了一个简单的java版本的单链表,链表反转和链表是否相交如果相交求相交节点。关于链表是否相交是一次阿里的面试的在线试题,挂的很彻底。然后就在网上找了几个实现思路自己用java做了一个简单的实现....

    我的Java单链表练习

    单链表作为最简单、最常见的数据结构之一,是每位程序员都应该掌握的基本技能。本文以“我的Java单链表练习”为主题,通过博主baby69yy2000在iteye上的博客分享,深入探讨了Java中实现单链表的相关知识。 首先,...

    算法各大公司的笔试题目算法部分之单链表的各种逆置排序.txt

    对于求职者而言,掌握单链表的相关算法不仅能够提高自己的编程能力,还能在面试中脱颖而出。本文将详细介绍几种常见的单链表逆置与排序算法,并提供Java代码示例。 #### 基础概念 在深入探讨具体算法之前,我们先来...

    python-leetcode面试题解之第369题给单链表加一.zip

    在本压缩包中,我们关注的是一个Python编程相关的面试题,源自著名的在线编程挑战平台LeetCode。题目编号为第369题,题目是“给单链表加一”。这是一道涉及数据结构和算法的问题,主要考察的是链表操作和数值计算。...

    2013年IT面试之百度笔试面试大礼包

    编程题目则涉及算法设计与实现,例如单链表的反转、数组中的公共元素查找以及逻辑推理题目,如确定最少老鼠数量以在一周内找出毒酒桶的问题。 ### 知识点三:百度面试题目分享 面试题目涵盖研发、QA、运维DBA等...

    算法分析_有无头结点的单链表的逆序和插入排序问题集源码微软面试题总结

    本文将深入探讨标题和描述中提到的两个关键概念:有无头结点的单链表的逆序以及插入排序,这些都是在面试中,尤其是像微软这样的顶级科技公司面试时常见的问题。 首先,我们来理解单链表的概念。单链表是一种线性...

Global site tag (gtag.js) - Google Analytics