2025年牛客鏈面試題及答案本文借鑒了近年相關(guān)經(jīng)典試題創(chuàng)作而成，力求幫助考生深入理解測試題型，掌握答題技巧，提升應(yīng)試能力。---2025年?？玩溍嬖囶}及答案一、編程題1.鏈表反轉(zhuǎn)題目描述：給定一個(gè)單鏈表的頭節(jié)點(diǎn)`head`，請將其反轉(zhuǎn)并返回反轉(zhuǎn)后的鏈表頭節(jié)點(diǎn)。示例：```輸入：head=[1,2,3,4,5]輸出：[5,4,3,2,1]```代碼要求：-使用遞歸或迭代的方式實(shí)現(xiàn)。-時(shí)間復(fù)雜度：O(n)-空間復(fù)雜度：O(1)參考代碼（迭代）：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverseList(head:ListNode)->ListNode:prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev```答案與解析：-反轉(zhuǎn)鏈表是鏈表操作中的經(jīng)典問題，可以通過迭代或遞歸實(shí)現(xiàn)。-迭代法：使用三個(gè)指針`prev`、`current`和`next_node`，逐個(gè)節(jié)點(diǎn)反轉(zhuǎn)鏈表方向。-遞歸法：遞歸到鏈表末尾，然后逐層返回時(shí)反轉(zhuǎn)鏈表方向。-時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)（迭代法）或O(n)（遞歸法）。---2.刪除排序鏈表中的重復(fù)元素題目描述：給定一個(gè)排序鏈表的頭節(jié)點(diǎn)`head`，刪除所有重復(fù)的元素，使得每個(gè)元素只出現(xiàn)一次。返回刪除重復(fù)元素后的鏈表。示例：```輸入：head=[1,1,2,3,3,4,4,5,5]輸出：[1,2,3,4,5]```代碼要求：-不使用額外空間。-時(shí)間復(fù)雜度：O(n)-空間復(fù)雜度：O(1)參考代碼：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefdeleteDuplicates(head:ListNode)->ListNode:current=headwhilecurrentandcurrent.next:ifcurrent.val==current.next.val:current.next=current.next.nextelse:current=current.nextreturnhead```答案與解析：-刪除排序鏈表中的重復(fù)元素可以通過雙指針法實(shí)現(xiàn)。-使用兩個(gè)指針`current`和`current.next`，比較相鄰節(jié)點(diǎn)的值。-如果相鄰節(jié)點(diǎn)的值相同，則將`current.next`指向下一個(gè)不同的節(jié)點(diǎn)。-時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。---3.環(huán)形鏈表判斷題目描述：給定一個(gè)鏈表的頭節(jié)點(diǎn)`head`，判斷鏈表中是否存在環(huán)。如果存在環(huán)，返回`true`；否則，返回`false`。示例：```輸入：head=[3,2,0,-4],pos=1輸出：true解釋：鏈表中有環(huán)，環(huán)的起始節(jié)點(diǎn)為第2個(gè)節(jié)點(diǎn)。```代碼要求：-使用快慢指針法。-時(shí)間復(fù)雜度：O(n)-空間復(fù)雜度：O(1)參考代碼：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefhasCycle(head:ListNode)->bool:ifnotheadornothead.next:returnFalseslow=headfast=head.nextwhileslow!=fast:ifnotfastornotfast.next:returnFalseslow=slow.nextfast=fast.next.nextreturnTrue```答案與解析：-判斷環(huán)形鏈表可以使用快慢指針法（Floyd'sTortoiseandHare）。-使用兩個(gè)指針`slow`和`fast`，`slow`每次移動一步，`fast`每次移動兩步。-如果鏈表中存在環(huán)，`fast`最終會追上`slow`。-如果`fast`或`fast.next`為空，則鏈表中不存在環(huán)。-時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。---4.鏈表相交題目描述：給定兩個(gè)單鏈表`headA`和`headB`，如果兩個(gè)鏈表相交，返回相交的起始節(jié)點(diǎn)；否則，返回`null`。示例：```輸入：headA=[1,3,5,7,9,11],headB=[2,4,6,8,10],intersectVal=8,listA=3,listB=1輸出：相交節(jié)點(diǎn)```代碼要求：-不使用額外空間。-時(shí)間復(fù)雜度：O(n)-空間復(fù)雜度：O(1)參考代碼：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefgetIntersectionNode(headA:ListNode,headB:ListNode)->ListNode:ifnotheadAornotheadB:returnNonea,b=headA,headBwhilea!=b:a=a.nextifaelseheadBb=b.nextifbelseheadAreturna```答案與解析：-鏈表相交問題可以通過雙指針法解決。-兩個(gè)指針分別從兩個(gè)鏈表的頭節(jié)點(diǎn)開始，當(dāng)走到鏈表末尾時(shí)，跳轉(zhuǎn)到另一個(gè)鏈表的頭節(jié)點(diǎn)。-如果兩個(gè)鏈表相交，指針最終會在相交節(jié)點(diǎn)相遇；否則，會在末尾都為`null`時(shí)相遇。-時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。---5.兩數(shù)相加題目描述：給出兩個(gè)非空的鏈表用來表示兩個(gè)非負(fù)的整數(shù)。其中，它們各自的位數(shù)是按照逆序的方式存儲的，并且它們的每個(gè)節(jié)點(diǎn)只能存儲一位數(shù)字。如果，我們將這兩個(gè)數(shù)相加起來，則會返回一個(gè)新的鏈表來表示它們的和。您可以假設(shè)除了數(shù)字0之外，這兩個(gè)數(shù)都不會以0開頭。示例：```輸入：(2->4->3)+(5->6->4)輸出：7->0->8解釋：342+465=807.```代碼要求：-使用遞歸或迭代的方式實(shí)現(xiàn)。-時(shí)間復(fù)雜度：O(max(m,n))-空間復(fù)雜度：O(max(m,n))參考代碼（迭代）：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefaddTwoNumbers(l1:ListNode,l2:ListNode)->ListNode:dummy_head=ListNode(0)current=dummy_headcarry=0whilel1orl2orcarry:val1=l1.valifl1else0val2=l2.valifl2else0sum_val=val1+val2+carrycarry=sum_val//10current.next=ListNode(sum_val%10)current=current.nextifl1:l1=l1.nextifl2:l2=l2.nextreturndummy_head.next```答案與解析：-兩數(shù)相加可以通過模擬加法過程實(shí)現(xiàn)。-使用一個(gè)虛擬頭節(jié)點(diǎn)`dummy_head`，并使用`carry`記錄進(jìn)位。-逐位相加，并將結(jié)果存儲在新鏈表中。-時(shí)間復(fù)雜度為O(max(m,n))，空間復(fù)雜度為O(max(m,n))。---二、算法題1.合并K個(gè)排序鏈表題目描述：合并k個(gè)排序鏈表，返回合并后的排序鏈表。請嘗試優(yōu)化算法，減少時(shí)間復(fù)雜度。示例：```輸入：lists=[[1,4,5],[1,3,4],[2,6]]輸出：1->1->2->3->4->4->5->6```代碼要求：-使用最小堆（優(yōu)先隊(duì)列）優(yōu)化。-時(shí)間復(fù)雜度：O(nlogk)-空間復(fù)雜度：O(k)參考代碼：```pythonimportheapqfromtypingimportList,OptionalclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmergeKLists(lists:List[Optional[ListNode]])->Optional[ListNode]:min_heap=[]forindex,nodeinenumerate(lists):ifnode:heapq.heappush(min_heap,(node.val,index,node))dummy_head=ListNode(0)current=dummy_headwhilemin_heap:val,idx,node=heapq.heappop(min_heap)current.next=nodecurrent=current.nextifnode.next:heapq.heappush(min_heap,(node.next.val,idx,node.next))returndummy_head.next```答案與解析：-合并K個(gè)排序鏈表可以使用最小堆（優(yōu)先隊(duì)列）優(yōu)化。-將每個(gè)鏈表的頭節(jié)點(diǎn)放入最小堆中，每次彈出最小節(jié)點(diǎn)，并將其下一個(gè)節(jié)點(diǎn)放入堆中。-時(shí)間復(fù)雜度為O(nlogk)，空間復(fù)雜度為O(k)。---2.劍指Offer52.丑數(shù)題目描述：把只包含質(zhì)因子2、3和5的數(shù)稱作丑數(shù)（UglyNumber）。求按從小到大的順序的第n個(gè)丑數(shù)。示例：```輸入：n=10輸出：12解釋：丑數(shù)序列為[1,2,3,4,5,6,8,9,10,12]```代碼要求：-使用動態(tài)規(guī)劃。-時(shí)間復(fù)雜度：O(n)-空間復(fù)雜度：O(n)參考代碼：```pythondefnthUglyNumber(n:int)->int:dp=[0]ndp[0]=1i2=i3=i5=0foriinrange(1,n):dp[i]=min(dp[i2]2,dp[i3]3,dp[i5]5)ifdp[i]==dp[i2]2:i2+=1ifdp[i]==dp[i3]3:i3+=1ifdp[i]==dp[i5]5:i5+=1returndp[-1]```答案與解析：-丑數(shù)問題可以使用動態(tài)規(guī)劃解決。-使用三個(gè)指針`i2`、`i3`和`i5`分別指向下一個(gè)丑數(shù)的倍數(shù)為2、3和5的位置。-每次選擇最小的值作為下一個(gè)丑數(shù)，并移動對應(yīng)的指針。-時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。---3.劍指Offer33.二叉搜索樹中的最近公共祖先題目描述：給定一個(gè)二叉搜索樹，找出其中值最小的節(jié)點(diǎn)。示例：```輸入：root=[2,2,5,null,null,5,7]輸出：2```代碼要求：-使用遞歸或迭代的方式實(shí)現(xiàn)。-時(shí)間復(fù)雜度：O(n)-空間復(fù)雜度：O(h)參考代碼（遞歸）：```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdeflowestCommonAncestor(root:TreeNode,p:TreeNode,q:TreeNode)->TreeNode:ifrootisNoneorroot==porroot==q:returnrootleft=lowestCommonAncestor(root.left,p,q)right=lowestCommonAncestor(root.right,p,q)ifleftandright:returnrootreturnleftifleftelseright```答案與解析：-二叉搜索樹中的最近公共祖先問題可以利用二叉搜索樹的性質(zhì)解決。-如果`p`和`q`的值都小于根節(jié)點(diǎn)的值，則公共祖先在左子樹中。-如果`p`和`q`的值都大于根節(jié)點(diǎn)的值，則公共祖先在右子樹中。-如果`p`和`q`的值分別小于和大于根節(jié)點(diǎn)的值，則根節(jié)點(diǎn)為公共祖先。-時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(h)。---4.劍指Offer21.調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面題目描述：輸入一個(gè)整數(shù)數(shù)組，實(shí)現(xiàn)一個(gè)函數(shù)來調(diào)整該數(shù)組，使得所有奇數(shù)位于數(shù)組的前面部分，所有偶數(shù)位于數(shù)組的后面部分。相對順序不能改變。示例：```輸入：nums=[1,2,3,4]輸出：[1,3,2,4]```代碼要求：-使用雙指針法。-時(shí)間復(fù)雜度：O(n)-空間復(fù)雜度：O(1)參考代碼：```pythondefexchange(nums:List[int])->List[int]:left,right=0,len(nums)-1whileleft<right:whileleft<rightandnums[left]%2!=0:left+=1whileleft<rightandnums[right]%2==0:right-=1nums[left],nums[right]=nums[right],nums[left]returnnums```答案與解析：-調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面可以使用雙指針法。-使用兩個(gè)指針`left`和`right`，`left`從左向右移動，`right`從右向左移動。-當(dāng)`left`指向偶數(shù)，`right`指向奇數(shù)時(shí)，交換這兩個(gè)數(shù)。-時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。---5.劍指Offer26.樹的子結(jié)構(gòu)題目描述：給定兩棵樹A和B，判斷樹B是否為樹A的子結(jié)構(gòu)。示例：```樹A:3/\45/\12樹B:4/1輸出：true```代碼要求：-使用遞歸的方式實(shí)現(xiàn)。-時(shí)間復(fù)雜度：O(nm)-空間復(fù)雜度：O(n)參考代碼：```pythonclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefisSubStructure(A:TreeNode,B:TreeNode)->bool:ifnotAornotB:returnFalseifA.val==B.val:ifisSameTree(A,B):returnTruereturnisSubStructure(A.left,B)orisSubStructure(A.right,B)defisSameTree(A:TreeNode,B:TreeNode)->bool:ifnotAandnotB:returnTrueifnotAornotB:returnFalseifA.val!=B.val:returnFalsereturnisSameTree(A.left,B.left)andisSameTree(A.right,B.right)```答案與解析：-樹的子結(jié)構(gòu)問題可以通過遞歸的方式解決。-首先判斷樹A和樹B的根節(jié)點(diǎn)是否相同，如果相同則進(jìn)一步判斷兩棵樹是否相同。-如果根節(jié)點(diǎn)不相同，則分別判斷樹A的左子樹和右子樹是否包含樹B。-時(shí)間復(fù)雜度為O(nm)，空間復(fù)雜度為O(n)。---三、系統(tǒng)設(shè)計(jì)題1.設(shè)計(jì)一個(gè)簡單的微博系統(tǒng)題目描述：設(shè)計(jì)一個(gè)簡單的微博系統(tǒng)，需要支持以下功能：-用戶注冊和登錄。-發(fā)布微博。-獲取用戶的時(shí)間線（自己的微博和關(guān)注的人的微博）。-關(guān)注和取消關(guān)注用戶。要求：-說明系統(tǒng)架構(gòu)。-數(shù)據(jù)庫設(shè)計(jì)。-使用的主要技術(shù)和工具。參考答案：-系統(tǒng)架構(gòu)：-前端：使用React或Vue.js構(gòu)建用戶界面。-后端：使用Node.js或SpringBoot構(gòu)建API。-數(shù)據(jù)庫：使用MySQL或MongoDB存儲用戶信息和微博數(shù)據(jù)。-緩存：使用Redis緩存熱點(diǎn)數(shù)據(jù)，提高系統(tǒng)性能。-消息隊(duì)列：使用Kafka或RabbitMQ處理異步任務(wù)，如通知推送。-數(shù)據(jù)庫設(shè)計(jì)：-用戶表：```sqlCREATETABLEusers(idINTAUTO_INCREMENTPRIMARYKEY,usernameVARCHAR(50)UNIQUENOTNULL,passwordVARCHAR(255)NOTNULL,created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP);```-微博表：```sqlCREATETABLEtweets(idINTAUTO_INCREMENTPRIMARYKEY,user_idINT,contentTEXTNOTNULL,created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP,FOREIGNKEY(user_id)REFERENCESusers(id));```-關(guān)注表：```sqlCREATETABLEfollows(follower_idINT,followee_idINT,created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP,PRIMARYKEY(follower_id,followee_id),FOREIGNKEY(follower_id)REFERENCESusers(id),FOREIGNKEY(followee_id)REFERENCESusers(id));```-使用的主要技術(shù)和工具：-前端：React或Vue.js。-后端：Node.js或SpringBoot。-數(shù)據(jù)庫：MySQL或MongoDB。-緩存：Redis。-消息隊(duì)列：Kafka或RabbitMQ。---2.設(shè)計(jì)一個(gè)短鏈接系統(tǒng)題目描述：設(shè)計(jì)一個(gè)短鏈接系統(tǒng)，需要支持以下功能：-用戶輸入長鏈接，系統(tǒng)生成短鏈接。-用戶通過短鏈接訪問長鏈接。-統(tǒng)計(jì)短鏈接的訪問次數(shù)。要求：-說明系統(tǒng)架構(gòu)。-數(shù)據(jù)庫設(shè)計(jì)。-使用的主要技術(shù)和工具。參考答案：-系統(tǒng)架構(gòu)：-前端：使用HTML和CSS構(gòu)建用戶界面。-后端：使用Go或Python構(gòu)建API。-數(shù)據(jù)庫：使用Redis存儲短鏈接和長鏈接的映射關(guān)系，以及訪問次數(shù)。-緩存：使用Nginx或HAProxy反向代理，提高系統(tǒng)性能和可用性。-數(shù)據(jù)庫設(shè)計(jì)：-短鏈接表：```sqlCREATETABLEshort_links(idINTAUTO_INCREMENTPRIMARYKEY,long_urlVARCHAR(255)NOTNULL,short_codeVARCHAR(10)UNIQUENOTNULL,created_atTIMESTAMPDEFAULTCURRENT_TIMESTAMP,access_countINTDEFAULT0);```-使用的主要技術(shù)和工具：-前端：HTML和CSS。-后端：Go或Python。-數(shù)據(jù)庫：Redis。-緩存：Nginx或HAProxy。---四、答案與解析編程題1.鏈表反轉(zhuǎn)-答案：如參考代碼所示，使用迭代法反轉(zhuǎn)鏈表。-解析：迭代法通過三個(gè)指針`prev`、`current`和`next_node`，逐個(gè)節(jié)點(diǎn)反轉(zhuǎn)鏈表方向。2.刪除排序鏈表中的重復(fù)元素-答案：如參考代碼所示，使用雙指針法刪除重復(fù)元素。-解析：雙指針法通過比較相鄰節(jié)點(diǎn)的值，如果相同則將`current.next`指向下一個(gè)不同的節(jié)點(diǎn)。3.環(huán)形鏈表判斷-答案：如參考代碼所示，使用快慢指針法判斷環(huán)形鏈表。-解析：快慢指針法通過兩個(gè)指針`slow`和`fast`，`slow`每次移動一步，`fast`每次移動兩步，如果鏈表中存在環(huán)，`fast`最終會追上`slow`。4.鏈表相交-答案：如參考代碼所示，使用雙指針法判斷鏈表相交。-解析：雙指針法通過兩個(gè)指針分別從兩個(gè)鏈表的頭節(jié)點(diǎn)開始，當(dāng)走到鏈表末尾時(shí)，跳轉(zhuǎn)到另一個(gè)鏈表的頭節(jié)點(diǎn)，如果兩個(gè)鏈表相交，指針最終會在相交節(jié)點(diǎn)相遇。5.兩數(shù)相加-答案：如參考代碼所示，使用迭代法相加兩個(gè)鏈表。-解析：迭代法通過模擬加法過程，逐位相加，并將結(jié)果存儲在新鏈表中。算法題1.