2025年牛客鏈面試題及答案本文借鑒了近年相關(guān)經(jīng)典試題創(chuàng)作而成，力求幫助考生深入理解測(cè)試題型，掌握答題技巧，提升應(yīng)試能力。---2025年?？玩溍嬖囶}及答案一、編程題1.鏈表反轉(zhuǎn)題目描述：給定一個(gè)單鏈表的頭節(jié)點(diǎn)`head`，請(qǐng)將其反轉(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)典問(wèn)題，可以通過(guò)迭代或遞歸實(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ù)元素可以通過(guò)雙指針?lè)▽?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解釋?zhuān)烘湵碇杏协h(huán)，環(huán)的起始節(jié)點(diǎn)為第2個(gè)節(jié)點(diǎn)。```代碼要求：-使用快慢指針?lè)ā?時(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)形鏈表可以使用快慢指針?lè)ǎ‵loyd'sTortoiseandHare）。-使用兩個(gè)指針`slow`和`fast`，`slow`每次移動(dòng)一步，`fast`每次移動(dòng)兩步。-如果鏈表中存在環(huán)，`fast`最終會(huì)追上`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```答案與解析：-鏈表相交問(wèn)題可以通過(guò)雙指針?lè)ń鉀Q。-兩個(gè)指針?lè)謩e從兩個(gè)鏈表的頭節(jié)點(diǎn)開(kāi)始，當(dāng)走到鏈表末尾時(shí)，跳轉(zhuǎn)到另一個(gè)鏈表的頭節(jié)點(diǎn)。-如果兩個(gè)鏈表相交，指針最終會(huì)在相交節(jié)點(diǎn)相遇；否則，會(huì)在末尾都為`null`時(shí)相遇。-時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。---5.兩數(shù)相加題目描述：給出兩個(gè)非空的鏈表用來(lái)表示兩個(gè)非負(fù)的整數(shù)。其中，它們各自的位數(shù)是按照逆序的方式存儲(chǔ)的，并且它們的每個(gè)節(jié)點(diǎn)只能存儲(chǔ)一位數(shù)字。如果，我們將這兩個(gè)數(shù)相加起來(lái)，則會(huì)返回一個(gè)新的鏈表來(lái)表示它們的和。您可以假設(shè)除了數(shù)字0之外，這兩個(gè)數(shù)都不會(huì)以0開(kāi)頭。示例：```輸入：(2->4->3)+(5->6->4)輸出：7->0->8解釋?zhuān)?42+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ù)相加可以通過(guò)模擬加法過(guò)程實(shí)現(xiàn)。-使用一個(gè)虛擬頭節(jié)點(diǎn)`dummy_head`，并使用`carry`記錄進(jìn)位。-逐位相加，并將結(jié)果存儲(chǔ)在新鏈表中。-時(shí)間復(fù)雜度為O(max(m,n))，空間復(fù)雜度為O(max(m,n))。---二、算法題1.合并K個(gè)排序鏈表題目描述：合并k個(gè)排序鏈表，返回合并后的排序鏈表。請(qǐng)嘗試優(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ù)稱(chēng)作丑數(shù)（UglyNumber）。求按從小到大的順序的第n個(gè)丑數(shù)。示例：```輸入：n=10輸出：12解釋?zhuān)撼髷?shù)序列為[1,2,3,4,5,6,8,9,10,12]```代碼要求：-使用動(dòng)態(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ù)問(wèn)題可以使用動(dòng)態(tài)規(guī)劃解決。-使用三個(gè)指針`i2`、`i3`和`i5`分別指向下一個(gè)丑數(shù)的倍數(shù)為2、3和5的位置。-每次選擇最小的值作為下一個(gè)丑數(shù)，并移動(dòng)對(duì)應(yīng)的指針。-時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)。---3.劍指Offer33.二叉搜索樹(shù)中的最近公共祖先題目描述：給定一個(gè)二叉搜索樹(shù)，找出其中值最小的節(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```答案與解析：-二叉搜索樹(shù)中的最近公共祖先問(wèn)題可以利用二叉搜索樹(shù)的性質(zhì)解決。-如果`p`和`q`的值都小于根節(jié)點(diǎn)的值，則公共祖先在左子樹(shù)中。-如果`p`和`q`的值都大于根節(jié)點(diǎn)的值，則公共祖先在右子樹(shù)中。-如果`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ù)來(lái)調(diào)整該數(shù)組，使得所有奇數(shù)位于數(shù)組的前面部分，所有偶數(shù)位于數(shù)組的后面部分。相對(duì)順序不能改變。示例：```輸入：nums=[1,2,3,4]輸出：[1,3,2,4]```代碼要求：-使用雙指針?lè)ā?時(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ù)前面可以使用雙指針?lè)ā?使用兩個(gè)指針`left`和`right`，`left`從左向右移動(dòng)，`right`從右向左移動(dòng)。-當(dāng)`left`指向偶數(shù)，`right`指向奇數(shù)時(shí)，交換這兩個(gè)數(shù)。-時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。---5.劍指Offer26.樹(shù)的子結(jié)構(gòu)題目描述：給定兩棵樹(shù)A和B，判斷樹(shù)B是否為樹(shù)A的子結(jié)構(gòu)。示例：```樹(shù)A:3/\45/\12樹(shù)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)```答案與解析：-樹(shù)的子結(jié)構(gòu)問(wèn)題可以通過(guò)遞歸的方式解決。-首先判斷樹(shù)A和樹(shù)B的根節(jié)點(diǎn)是否相同，如果相同則進(jìn)一步判斷兩棵樹(shù)是否相同。-如果根節(jié)點(diǎn)不相同，則分別判斷樹(shù)A的左子樹(shù)和右子樹(shù)是否包含樹(shù)B。-時(shí)間復(fù)雜度為O(nm)，空間復(fù)雜度為O(n)。---三、系統(tǒng)設(shè)計(jì)題1.設(shè)計(jì)一個(gè)簡(jiǎn)單的微博系統(tǒng)題目描述：設(shè)計(jì)一個(gè)簡(jiǎn)單的微博系統(tǒng)，需要支持以下功能：-用戶(hù)注冊(cè)和登錄。-發(fā)布微博。-獲取用戶(hù)的時(shí)間線(xiàn)（自己的微博和關(guān)注的人的微博）。-關(guān)注和取消關(guān)注用戶(hù)。要求：-說(shuō)明系統(tǒng)架構(gòu)。-數(shù)據(jù)庫(kù)設(shè)計(jì)。-使用的主要技術(shù)和工具。參考答案：-系統(tǒng)架構(gòu)：-前端：使用React或Vue.js構(gòu)建用戶(hù)界面。-后端：使用Node.js或SpringBoot構(gòu)建API。-數(shù)據(jù)庫(kù)：使用MySQL或MongoDB存儲(chǔ)用戶(hù)信息和微博數(shù)據(jù)。-緩存：使用Redis緩存熱點(diǎn)數(shù)據(jù)，提高系統(tǒng)性能。-消息隊(duì)列：使用Kafka或RabbitMQ處理異步任務(wù)，如通知推送。-數(shù)據(jù)庫(kù)設(shè)計(jì)：-用戶(hù)表：```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ù)庫(kù)：MySQL或MongoDB。-緩存：Redis。-消息隊(duì)列：Kafka或RabbitMQ。---2.設(shè)計(jì)一個(gè)短鏈接系統(tǒng)題目描述：設(shè)計(jì)一個(gè)短鏈接系統(tǒng)，需要支持以下功能：-用戶(hù)輸入長(zhǎng)鏈接，系統(tǒng)生成短鏈接。-用戶(hù)通過(guò)短鏈接訪(fǎng)問(wèn)長(zhǎng)鏈接。-統(tǒng)計(jì)短鏈接的訪(fǎng)問(wèn)次數(shù)。要求：-說(shuō)明系統(tǒng)架構(gòu)。-數(shù)據(jù)庫(kù)設(shè)計(jì)。-使用的主要技術(shù)和工具。參考答案：-系統(tǒng)架構(gòu)：-前端：使用HTML和CSS構(gòu)建用戶(hù)界面。-后端：使用Go或Python構(gòu)建API。-數(shù)據(jù)庫(kù)：使用Redis存儲(chǔ)短鏈接和長(zhǎng)鏈接的映射關(guān)系，以及訪(fǎng)問(wèn)次數(shù)。-緩存：使用Nginx或HAProxy反向代理，提高系統(tǒng)性能和可用性。-數(shù)據(jù)庫(kù)設(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ù)庫(kù)：Redis。-緩存：Nginx或HAProxy。---四、答案與解析編程題1.鏈表反轉(zhuǎn)-答案：如參考代碼所示，使用迭代法反轉(zhuǎn)鏈表。-解析：迭代法通過(guò)三個(gè)指針`prev`、`current`和`next_node`，逐個(gè)節(jié)點(diǎn)反轉(zhuǎn)鏈表方向。2.刪除排序鏈表中的重復(fù)元素-答案：如參考代碼所示，使用雙指針?lè)▌h除重復(fù)元素。-解析：雙指針?lè)ㄍㄟ^(guò)比較相鄰節(jié)點(diǎn)的值，如果相同則將`current.next`指向下一個(gè)不同的節(jié)點(diǎn)。3.環(huán)形鏈表判斷-答案：如參考代碼所示，使用快慢指針?lè)ㄅ袛喹h(huán)形鏈表。-解析：快慢指針?lè)ㄍㄟ^(guò)兩個(gè)指針`slow`和`fast`，`slow`每次移動(dòng)一步，`fast`每次移動(dòng)兩步，如果鏈表中存在環(huán)，`fast`最終會(huì)追上`slow`。4.鏈表相交-答案：如參考代碼所示，使用雙指針?lè)ㄅ袛噫湵硐嘟弧?解析：雙指針?lè)ㄍㄟ^(guò)兩個(gè)指針?lè)謩e從兩個(gè)鏈表的頭節(jié)點(diǎn)開(kāi)始，當(dāng)走到鏈表末尾時(shí)，跳轉(zhuǎn)到另一個(gè)鏈表的頭節(jié)點(diǎn)，如果兩個(gè)鏈表相交，指針最終會(huì)在相交節(jié)點(diǎn)相遇。5.兩數(shù)相加-答案：如參考代碼所示，使用迭代法相加兩個(gè)鏈表。-解析：迭代法通過(guò)模擬加法過(guò)程，逐位相加，并將結(jié)果存儲(chǔ)在新鏈表中。算法題1.