您当前的位置:首页 > 电脑百科 > 数据库 > 百科

七道经典的关于链表的笔试题目

时间:2020-09-29 09:56:22  来源:  作者:

给定一个带有头节点的单链表,如何将其逆序,也就是说head->a->b->c,变为head->c->b->a?

难点:这个需要了解链表的结构,每一个链表除了存储自身的元素之外,还会存储下一个结点的地址,所以要想遍历链表需要从头结点开始,还要注意一旦要是修改了当前结点存储的下一节点的地址,如果我们不使用一个变量记录这个地址,那么后面的链表就会丢失了,所以我们时时刻刻都不能忘记,当前结点的下一个结点的地址。

时间复杂度为O(N)

解决方法:插入法

核心思想是遍历链表,每遍历到一个结点就将其插入到头节点之后,作为头结点之后的第一个结点,比如遍历到b,那么此时它需要把b拿出来放到head后面,并且将a的后继结点的改为c,此时链表变为head->b->a->c,这样遍历完一遍之后就可以了,不用第二遍,而且不需要额外的地址。

代码实现:

class ListNode():
    def __init__(self):        self.data=None        self.next=next
def reverse(ListNode):
    if ListNode is None and ListNode.next is None:
        return
    #获取第二个(当前)    cur=ListNode.next.next
    ListNode.next.next=None
    nextNode=None    while cur is not None:
        nextNode=cur.next
        cur.next=ListNode.next
        ListNode.next=cur
        cur=nextNodeif __name__ =="__main__" :
    LNode=ListNode()    p=LNode    LNode.data=None    LNode.next=None
    i=1
    while i<=10:
        L=ListNode()        L.data=i        L.next=None
        p.next=L
        p=L        i=i+1
    cur=LNode.next
    while cur is not None:
        print(cur.data)
        cur=cur.next
    reverse(LNode)
    print("反转后")
    cur=LNode.next
    while cur is not None:
        print(cur.data)
        cur=cur.next

逆序输出链表

给定一个链表,然后逆序输出,比如有一个链表head->a->b->c,那么此时我们希望输出c,b,a

我们可以使用递归的形式,(a,b,c)先输出(b,c),然后(b,c)先输出c

时间复杂度O(N)

class Node():
    def __init__(self):
        self.next=None
        self.data=Nonedef  ReserverPrint(List):    if List is None:
        return
    ReserverPrint(List.next)    print(List.data)if __name__=="__main__":
    LNode=Node()    p=LNode    i=1
    while i<10:
        l=Node()        l.data=i        l.next=None
        p.next=l        p=l        i+=1
    cur=LNode.next    while cur is not None:
        print(cur.data)        cur=cur.next    #反转输出
    print("反转输出")
    ReserverPrint(LNode.next)

对链表进行重新排序

现在有一个链表为head->1->2->3->4->5->6->7,排序之后head->1->7->2->6->3->5->4

我们分析一下,可以看到实际上原始序列的前半部分并没有发生改变,而后半部分是逆序,然后将两个一个一个的插入了,所以说这个的核心是先将后半部分逆序,然后两个链表同时遍历,一个一个的最终形成新的排序链表

七道经典的关于链表的笔试题目

 

这个的意思就是说pre用于指向链表1的第一个结点,cur永远指向链表2的第二个结点,最后返回第一个结点就可以了

class Node():
    def __init__(self):        self.data=None        self.next=None
def firstmiddle(list):    if list is None or list.next is None:
        return list
    first=list    two=list    while two is not None and two.next is not None:
        pre_first=first        first=first.next
        two=two.next.next
    pre_first.next=None
    return first
def reverse(list):
    if list is None or list.next is None:
        return list
    cur=list.next
    pre=list    n_next=cur.next
    pre.next=None#这个意思是形成两部分,第一部分有第一个结点->None,第二部分以第二个结点cur直到最后
    while cur is not None:
        a=cur.next
        cur.next=pre
        pre=cur        cur=a    return pre
def Recorder(list):    cur1=list.next
    mid=firstmiddle(list.next)
    cur2=reverse(mid)
    while cur1.next is not None:
        a=cur1.next#存储cur1,然后再将cur1找回来
        cur1.next=cur2
        cur1=a        a=cur2.next
        cur2.next=cur1
        cur2=a    cur1.next=cur2
if __name__=="__main__":
    listNode=Node()    p=listNode    i=1
    while i<=10:
        l=Node()        l.data=i        l.next=None
        p.next=l
        p=l        i+=1
    Recorder(listNode)    cur=listNode.next
    while cur is not None:
        print(cur.data)
        cur=cur.next

找到一个链表的中间元素

从头开始遍历链表,设置两个指针,其中一个指针每次走两步,另外一个指针每次走一步,那么当走两步的这个只能走到头的时候,那么此时走第一步的这个指针就是指向的中间的元素

设置一个指针one,然后设置一个指针two,two每次走两步,然后one每次走一步,当two走到头之后,one就走到中间了。

如果链表结点数为奇数,那么此时的one就是中间结点,如果链表结点数为偶数,那么此时的one和接下来的一个结点就是中间结点

class Node():
    def __init__(self):
        self.next=None
        self.data=Nonedef FindMiddleNode(ListNode):    if ListNode is None or ListNode.next is None:
        return ListNode
    one=ListNode    two=ListNode    while two is not None and two.next is not None:
        one=one.next        two=two.next.next    return one
if __name__=="__main__":
    ListNode=Node()    p=ListNode    i=0
    while i<10:
        l=Node()        l.next=None
        l.data=i        p.next=l        p=l        i+=1
    cur=ListNode.next    #原始的列表顺序输出
    while cur is not None:
        print(cur.data)
        cur=cur.next
    mid=FindMiddleNode(ListNode.next)
    print(mid.data)#输出中间的元素

将两个链表依次合并,现在有一个l1链表a->b->c,还有一个l2链表1->2->3,然后依次合并,此时合并的链表为a->1->b->2->c->3

这个步骤是这样的,主要是将l1链表为主链,思想如下图所示:

七道经典的关于链表的笔试题目

 

class Node():
    def __init__(self):        self.data=None        self.next=None
if __name__=="__main__":
    one_listNode=Node()    one_p=one_listNode    two_listNode = Node()    two_p = two_listNode    i=1
    while i<=10:
        l=Node()        l.data=i        l.next=None
        one_p.next=l
        one_p=l        i+=1
    j=11
    while j<=20:
        l=Node()        l.data=j        l.next=None
        two_p.next=l
        two_p=l        j+=1
    one=one_listNode.next
    two=two_listNode.next
    a=None    while one.next is not None:
        a=one.next
        one.next=two
        one=a        a=two.next
        two.next=one
        two=a    one.next=two
    n=one_listNode.next
    while n is not None:
        print(n.data)
        n=n.next

找到一个链表的倒数第k个结点

我们可以设置两个指针,其中一个指针领先第二个指针k个元素,当第一个指针到链表结尾了,那么第一个指针就是链表的倒数第k个结点。这个只需要遍历一次链表,所以时间复杂度为O(N)

需要注意的是,我们需要时时刻刻地判断这个链表是否长度能够到k,如果本身就没有k个元素,那么倒数第k个元素也是没有意义的

class Node():
    def __init__(self):        self.next=None        self.data=None
def FindlastK(list,k):    if list is None or list.next is None:
        return
    i=0
    klist=list    first=list    #klist比first领先3个元素
    while i<k and klist is not None:
        klist=klist.next        i+=1
    if i<k:#如果领先不到3个元素,那么就会出现问题
        return
    while klist is not None:
        klist=klist.next        first=first.next    return first
if __name__=="__main__":
    list=Node()    p=list    i=1
    k=3
    n=None    while i<=7:
        n=Node()        n.data=i
        n.next=None        p.next=n        p=n        i+=1
    first=FindlastK(list,k)    print(first.data)

单链表向右旋转k个位置

这个意思是这样的,现在有一个单链表头结点->1->2->3->4->5->6->7,此时我们设置k=3,那么我们希望链表可以变为:头结点->5->6->7->1->2->3->4。

这个我们可以先找到倒数第k+1个结点slow,以及原始链表的尾结点fast,然后分割为两个链表,然后进行组合就完成了单链表向右旋转k个位置

七道经典的关于链表的笔试题目

 

class Node():
    def __init__(self):        self.next=None
        self.data=Nonedef  RotateK(list,K):    if list is None or list.next is None:
        return
    slow=list.next
    fast=list.next
    i=0
    tmpend=None    tmpstart=None    while i<=K and fast is not None:
        fast=fast.next
        i+=1
    if i<K:#根本没有k个原元素
        return
    while fast is not None:
        tmpend=fast        fast=fast.next
        slow=slow.next
        tmpstart=slow.next
    slow.next=None#断成两条链,第一条链头的list,尾是slow,第二条链头是tmpstart,尾是tmpend
    #print(slow.data)
    #print(tmpend.data)
    #print(tmpstart.data)
    tmpend.next=list.next
    list.next=tmpstart
if __name__=="__main__":
    list=Node()    p=list    i=1
    K=3
    while i<=7:
        n=Node()        n.data=i        n.next=None
        p.next=n
        p=n        i+=1
    RotateK(list,K)    a=list.next
    while a is not None:
        print(a.data)
        a=a.next


Tags:链表   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
遵从所有教材以及各类数据结构相关的书书籍,我们先从线性表开始入门。今天这篇文章更偏概念,是关于有线性表的一个知识点的汇总。上文说过,物理结构是用于确定数据以何种方式存...【详细内容】
2021-07-19  Tags: 链表  点击:(94)  评论:(0)  加入收藏
当我们在聊到链表反转的时候,一定说的都是单链表,双链表本身就具有前驱指针 Prev 和后续指针 next,无需进行翻转。单链表反转,反转后的效果如下: 看起来很简单,只需要将单链表所...【详细内容】
2021-01-12  Tags: 链表  点击:(185)  评论:(0)  加入收藏
问题描述输入两个链表,找出它们的第一个公共节点。如下面的两个链表: 在节点 c1 开始相交。 示例 1: 输入:intersectVal = 8,listA = [4,1,8,4,5],listB = [5,0,1,8,4,5],skipA...【详细内容】
2020-10-19  Tags: 链表  点击:(124)  评论:(0)  加入收藏
给定一个带有头节点的单链表,如何将其逆序,也就是说head->a->b->c,变为head->c->b->a?难点:这个需要了解链表的结构,每一个链表除了存储自身的元素之外,还会存储下一个结点的地址,...【详细内容】
2020-09-29  Tags: 链表  点击:(118)  评论:(0)  加入收藏
数组作为一个顺序储存方式的数据结构,可是有大作为的,它的灵活使用为我们的程序设计带来了大量的便利;...【详细内容】
2020-08-31  Tags: 链表  点击:(54)  评论:(0)  加入收藏
什么是链表?当你用一个数组存放数据时就需要给它定义一个长度,如果定一个未知的数据,你就需要扩大数组的范围,有时如果由于某种特殊原因,数据增加,有需要重新修改程序,扩大数组的存...【详细内容】
2020-08-11  Tags: 链表  点击:(162)  评论:(0)  加入收藏
图的存储方式很多,常用的有邻接矩阵、邻接表、逆邻接表、十字链表、链式前向星等,邻接表和逆邻接表采用数组和链表方式存储,程序代码相对容易,邻接表求某顶点的出度容易但求入度...【详细内容】
2020-07-08  Tags: 链表  点击:(121)  评论:(0)  加入收藏
常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等。每一种数据结构都有着独特的数据存储方式,下面为大家介绍它们的结构和优缺点。1、数组 数组是可以再内存中连续存储多个元素...【详细内容】
2020-03-01  Tags: 链表  点击:(54)  评论:(0)  加入收藏
1 题目描述给定一个链表,移除其自末尾起第N个节点后返回该链表。例子:输入:给定链表1->2->3->4->5,且n=2输出:移除链表末尾起第2个节点4后,链表变为1->2->3->5。题目出处:https://...【详细内容】
2019-08-15  Tags: 链表  点击:(193)  评论:(0)  加入收藏
1. redis中的链表在redis中链表的应用非常广泛,例如列表键的底层实现之一就是链表。而且,在redis中的链表结构被实现成为双向链表,因此,在头部和尾部进行的操作就会非常快。通过...【详细内容】
2019-08-05  Tags: 链表  点击:(271)  评论:(0)  加入收藏
▌简易百科推荐
1增1.1【插入单行】insert [into] <表名> (列名) values (列值)例:insert into Strdents (姓名,性别,出生日期) values (&#39;开心朋朋&#39;,&#39;男&#39;,&#39;1980/6/15&#3...【详细内容】
2021-12-27  快乐火车9d3    Tags:SQL   点击:(1)  评论:(0)  加入收藏
最近发现还有不少做开发的小伙伴,在写存储过程的时候,在参考已有的不同的写法时,往往很迷茫, 不知道各种写法孰优孰劣,该选用哪种写法,以及各种写法的优缺点,本文以一个简单的查询...【详细内容】
2021-12-23  linux上的码农    Tags:sql   点击:(9)  评论:(0)  加入收藏
《开源精选》是我们分享Github、Gitee等开源社区中优质项目的栏目,包括技术、学习、实用与各种有趣的内容。本期推荐的HasorDB 是一个全功能数据库访问工具,提供对象映射、丰...【详细内容】
2021-12-22  GitHub精选    Tags:HasorDB   点击:(5)  评论:(0)  加入收藏
作者丨Rafal Grzegorczyk译者丨陈骏策划丨孙淑娟【51CTO.com原创稿件】您是否还在手动对数据库执行各种脚本?您是否还在浪费时间去验证数据库脚本的正确性?您是否还需要将...【详细内容】
2021-12-22    51CTO  Tags:Liquibase   点击:(3)  评论:(0)  加入收藏
场景描述:由于生产环境的表比较复杂,字段很多。这里我们做下简化,只为说明今天要聊的问题。有两张表 tab1,tab2: tab1 数据如下: tab2 数据如下: 然后给你看下,我用来统计 name=&#3...【详细内容】
2021-12-20  Bald    Tags:SQL   点击:(5)  评论:(0)  加入收藏
前言知识无底,学海无涯,知识点虽然简单,但是比较多,所以将MySQL的基础写出来,方便自己以后查找,还有就是分享给大家。一、SQL简述1.SQL的概述Structure Query Language(结构化查...【详细内容】
2021-12-16  谣言止于独立思考    Tags:SQL基础   点击:(13)  评论:(0)  加入收藏
前言作为一名测试工程师,工作中在对测试结果进行数据比对的时候,或多或少要和数据库打交道的,要和数据库打交道,那么一些常用的 SQL 查询语法必须要掌握。最近有部分做测试小伙...【详细内容】
2021-12-14  柠檬班软件测试    Tags:SQL   点击:(15)  评论:(0)  加入收藏
话说C是面向内存的编程语言。数据要能存得进去,取得出来,且要考虑效率。不管是顺序存储还是链式存储,其寻址方式总是很重要。顺序存储是连续存储。同质结构的数组通过其索引表...【详细内容】
2021-12-08  小智雅汇    Tags:数据存储   点击:(17)  评论:(0)  加入收藏
概述DBConvert Studio 是一款强大的跨数据库迁移和同步软件,可在不同数据库格式之间转换数据库结构和数据。它将成熟、稳定、久经考验的 DBConvert 和 DBSync 核心与改进的现...【详细内容】
2021-11-17  雪竹聊运维    Tags:数据库   点击:(26)  评论:(0)  加入收藏
一、前言 大家好,我是小诚,《从0到1-全面深刻理解MySQL系列》已经来到第四章,这一章节的主要从一条SQL执行的开始,由浅入深的解析SQL语句由客户端到服务器的完整执行流程,最...【详细内容】
2021-11-09  woaker    Tags:SQL   点击:(35)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条