江苏龙网

  1. 主页 > 生活百科 > >

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

链表

给定一个带有头节点的单链表，如何将其逆序，也就是说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=https://www.isolves.com/it/sjk/bk/2020-09-29/Noneself.next=nextdef reverse(ListNode):if ListNode is None and ListNode.next is None:return#获取第二个（当前）cur=ListNode.next.nextListNode.next.next=NonenextNode=Nonewhile cur is not None:nextNode=cur.nextcur.next=ListNode.nextListNode.next=curcur=nextNodeif __name__ =="__main__" :LNode=ListNode()p=LNodeLNode.data=NoneLNode.next=Nonei=1while i<=10:L=ListNode()L.data=iL.next=Nonep.next=Lp=Li=i+1cur=LNode.nextwhile cur is not None:print(cur.data)cur=cur.nextreverse(LNode)print("反转后")cur=LNode.nextwhile 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=Noneself.data=https://www.isolves.com/it/sjk/bk/2020-09-29/NonedefReserverPrint(List):if List is None:returnReserverPrint(List.next)print(List.data)if __name__=="__main__":LNode=Node()p=LNodei=1while i<10:l=Node()l.data=il.next=Nonep.next=lp=li+=1cur=LNode.nextwhile 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=https://www.isolves.com/it/sjk/bk/2020-09-29/Noneself.next=Nonedef firstmiddle(list):if list is None or list.next is None:return listfirst=listtwo=listwhile two is not None and two.next is not None:pre_first=firstfirst=first.nexttwo=two.next.nextpre_first.next=Nonereturn firstdef reverse(list):if list is None or list.next is None:return listcur=list.nextpre=listn_next=cur.nextpre.next=None#这个意思是形成两部分，第一部分有第一个结点->None,第二部分以第二个结点cur直到最后while cur is not None:a=cur.nextcur.next=prepre=curcur=areturn predef Recorder(list):cur1=list.nextmid=firstmiddle(list.next)cur2=reverse(mid)while cur1.next is not None:a=cur1.next#存储cur1，然后再将cur1找回来cur1.next=cur2cur1=aa=cur2.nextcur2.next=cur1cur2=acur1.next=cur2if __name__=="__main__":listNode=Node()p=listNodei=1while i<=10:l=Node()l.data=il.next=Nonep.next=lp=li+=1Recorder(listNode)cur=listNode.nextwhile 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=Noneself.data=https://www.isolves.com/it/sjk/bk/2020-09-29/Nonedef FindMiddleNode(ListNode):if ListNode is None or ListNode.next is None:return ListNodeone=ListNodetwo=ListNodewhile two is not None and two.next is not None:one=one.nexttwo=two.next.nextreturn oneif __name__=="__main__":ListNode=Node()p=ListNodei=0while i


推荐阅读


上一篇：利用python+opencv获取你的身份证信息

下一篇：没有了