2025年链表经典试题及答案

2025年链表经典试题及答案给定单链表头节点head和整数k（k≥1），要求将链表每k个节点一组进行反转，若剩余节点不足k个则保持原顺序。例如，输入链表1->2->3->4->5，k=2时，输出2->1->4->3->5；k=3时，输出3->2->1->4->5。解题思路需分三步：首先判断当前剩余节点数是否≥k，若不足则直接返回；若满足则反转前k个节点，然后递归处理剩余部分。反转过程中需记录反转后的新头节点、原头节点（反转后的尾节点）以及下一组的起始节点。关键在于正确连接反转后的子链表与后续部分，避免断链。Python代码实现：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverseKGroup(head:ListNode,k:int)->ListNode:检查剩余节点是否足够k个tail=headfor_inrange(k):ifnottail:returnheadtail=tail.next反转前k个节点（左闭右开区间[head,tail)）prev,curr=None,headwhilecurr!=tail:next_node=curr.nextcurr.next=prevprev,curr=curr,next_node原head变为反转后的尾节点，连接递归处理后的结果head.next=reverseKGroup(tail,k)returnprevprev是反转后的新头节点```关键点解析：通过提前遍历k步确定tail的位置，确保反转区间为[head,tail)。反转操作使用迭代法，逐个调整指针方向。递归调用时，原头节点的next指向后续处理结果，实现子链表的连接。时间复杂度O(n)（每个节点仅遍历两次：一次检查长度，一次反转），空间复杂度O(k)（递归栈深度，最坏情况k=n）。给定k个升序排列的单链表头节点数组lists（k≥1），要求合并成一个升序链表。例如，输入[[1,4,5],[1,3,4],[2,6]]，输出1->1->2->3->4->4->5->6。解题思路采用分治法：将k个链表两两分组，递归合并每组，最终合并为一个链表。分治策略可将时间复杂度从暴力合并的O(kn)（每次合并两个，共k-1次）优化为O(nklogk)（每轮合并n个节点，共logk轮）。Python代码实现：```pythondefmergeKLists(lists):defmergeTwo(a,b):dummy=ListNode()curr=dummywhileaandb:ifa.val<b.val:curr.next=aa=a.nextelse:curr.next=bb=b.nextcurr=curr.nextcurr.next=aifaelsebreturndummy.nextn=len(lists)ifn==0:returnNoneifn==1:returnlists[0]分治：分成左右两半合并mid=n//2left=mergeKLists(lists[:mid])right=mergeKLists(lists[mid:])returnmergeTwo(left,right)```关键点解析：mergeTwo函数实现两个有序链表的合并，使用哑节点简化头节点处理。分治时将链表数组不断二分，直到子问题规模为1，再逐层向上合并。相比优先队列（堆）方法，分治法无需额外空间存储堆结构（仅递归栈空间O(logk)），更适合处理大k值场景。给定单链表头节点head，判断是否存在环；若存在，返回环的入口节点；否则返回None。例如，链表3->2->0->4->2（环在2节点），入口节点为2。解题思路分两步：首先用快慢指针检测环（快指针每次走2步，慢指针每次走1步，若相遇则有环）；若有环，将慢指针移回头节点，快慢指针均每次走1步，再次相遇点即为入口。数学推导：设头节点到入口距离为a，入口到相遇点距离为b，环长度为L。快指针走的距离为a+b+nL（n≥1），慢指针走的距离为a+b。因快指针速度是慢指针的2倍，故a+b+nL=2(a+b)，得a=nLb。当慢指针从头节点出发走a步，快指针从相遇点出发走a步（即nLb步），两者会在入口节点相遇（快指针绕环n-1圈后到达入口）。Python代码实现：```pythondefdetectCycle(head:ListNode)->ListNode:slow=fast=head检测是否有环whilefastandfast.next:slow=slow.nextfast=fast.next.nextifslow==fast:breakelse:无环退出循环returnNone找入口节点slow=headwhileslow!=fast:slow=slow.nextfast=fast.nextreturnslow```关键点解析：快慢指针相遇时，快指针可能已绕环多圈，但数学推导保证了a与(nLb)的等价性。代码中需注意循环终止条件（fast和fast.next均不为空，避免空指针异常）。时间复杂度O(n)，空间复杂度O(1)。给定单链表头节点head和整数val，删除所有节点值等于val的节点，返回新头节点。例如，输入1->2->6->3->4->5->6，val=6，输出1->2->3->4->5。解题思路：使用哑节点（dummynode）简化头节点处理。哑节点的next指向原头节点，遍历链表时，若当前节点的下一个节点值为val，则跳过该节点（即curr.next=curr.next.next）；否则继续遍历。Python代码实现：```pythondefremoveElements(head:ListNode,val:int)->ListNode:dummy=ListNode(next=head)curr=dummywhilecurr.next:ifcurr.next.val==val:curr.next=curr.next.next删除下一个节点else:curr=curr.next否则移动当前节点returndummy.next```关键点解析：哑节点避免了单独处理头节点被删除的情况（如头节点值为val时）。循环条件为curr.next存在，直接检查下一个节点的值，若符合条件则跳过，否则移动curr指针。该方法可处理连续多个val的情况（如1->2->2->3，val=2时，连续删除两个2节点）。时间复杂度O(n)，空间复杂度O(1)。给定一个复杂链表，每个节点包含val、next和random指针（random指向链表中任意节点或None），要求复制该链表，返回新链表的头节点。例如，原节点A的random指向节点B，新节点A'的random应指向新节点B'。解题思路采用原地复制法（空间复杂度O(1)）：第一步，遍历原链表，将新节点插入原节点之后（如原链表A->B->C变为A->A'->B->B'->C->C'）；第二步，遍历新链表，设置新节点的random指针（原节点A的random为C，则新节点A'的random为C'，即原节点random的next）；第三步，拆分原链表和新链表，恢复原链表结构并提取新链表。Python代码实现：```pythonclassNode:def__init__(self,x:int,next:'Node'=None,random:'Node'=None):self.val=xself.next=nextself.random=randomdefcopyRandomList(head:'Node')->'Node':ifnothead:returnNone第一步：插入新节点curr=headwhilecurr:new_node=Node(curr.val,next=curr.next)curr.next=new_nodecurr=new_node.next第二步：设置random指针curr=headwhilecurr:ifcurr.random:curr.next.random=curr.random.nextcurr=curr.next.next第三步：拆分链表old=headnew_head=head.nextnew=new_headwhilenew.next:old.next=old.next.next恢复原链表new.next=new.next.next构建新链表old=old.nextnew=new.nextold.next=None处理原链表尾节点returnnew_head```关键点解析：插入新节点时需保存原next指针，避免断链。设置random指针时，若原节点的random为None，则新节点的random也为None。拆分时需同步移动原链表和新链表的指针，最后断开原链表尾节点的next（避免指向新链表节点）。时间复杂度O(n)，空间复杂度O(1)（仅使用常数额外空间）。给定两个单链表headA和headB，可能存在公共后缀（即相交于某一节点），要求找出第一个公共节点；若不相交则返回None。例如，headA为4->1->8->4->5，headB为5->0->1->8->4->5，公共节点为8。解题思路采用双指针法：设p1从headA出发，p2从headB出发。p1遍历完headA后转向headB，p2遍历完headB后转向headA。若两链表相交，p1和p2会在公共节点相遇；若不相交，最终均指向None。数学推导：设headA长度为m，headB长度为n，公共部分长度为c。则headA非公共部分长度为mc，headB非公共部分长度为nc。p1走的距离为(mc)+c+(nc)=m+nc，p2走的距离为(nc)+c+(mc)=m+nc，两者相等，故相遇于公共节点。若不相交（c=0），则p1走m+n步，p2走n+m步，最终均为None。Python代码实现：```pythondefgetIntersectionNode(headA:ListNode,headB:ListNode)->ListNode:p1,p2=headA,headBwhilep1!=p2:p1=p1.nextifp1elseheadBp2=p2.nextifp2elseheadAreturnp1```关键点解析：无需计算两链表长度，双指针通过自动转向消除长度差。代码简洁，时间复杂度O(m+n)，空间复杂度O(1)。若链表有环（本题假设无环），需先检测环并处理。给定单链表head，要求将其重排为L0->Ln->L1->Ln-1->...的形式。例如，输入1->2->3->4->5，重排后为1->5->2->4->3。解题思路分三步：找到链表中间节点（前半部分末尾），反转后半部分链表，然后交替合并前半部分和反转后的后半部分。Python代码实现：```pythondefreorderList(head:ListNode)->None:ifnotheadornothead.next:return找中间节点（前半部分末尾）slow,fast=head,head.nextwhilefastandfast.next:slow=slow.nextfast=fast.next.nextmid=slow反转后半部分（mid.next到末尾）prev,curr=None,mid.nextmid.next=None断开前后两部分whilecurr:next_node=curr.nextcurr.next=prevprev,curr=curr,next_node合并两部分（head和prev）first,second=head,prevwhilesecond:temp1,temp2=first.next,second.nextfirst.next=secondsecond.next=temp1first,second=temp1,temp2```关键点解析：找中间节点时，快指针初始化为head.next，确保当链表长度为偶数时，slow指向前半部分最后一个节点（如1->2->3->4，slow指向2）。反转后半部分后，断开原链表连接避免环。合并时交替连接两部分节点，直到后半部分遍历完毕。时间复杂度O(n)，空间复杂度O(1)。给定单链表head，要求对其进行升序排序，时间复杂度O(nlogn)，空间复杂度O(logn)（递归栈）或O(1)（迭代归并）。解题思路采用归并排序：递归分割链表为两部分，分别排序后合并。链表归并排序的优势在于无需随机访问（数组归并需额外空间复制），分割链表通过快慢指针找中间节点实现。Python代码实现（递归版）：```pythondefsortList(head:ListNode)->ListNode:ifnotheadornothead.next:returnhead找中间节点（前半部分末尾）slow,fast=head,head.nextwhilefastandfast.next:slow=slow.