單鏈編程題目及答案VIP

單鏈編程題目及答案題目一：鏈表反轉(zhuǎn)題目描述：給定一個單鏈表的頭節(jié)點`head`，請你反轉(zhuǎn)該鏈表，并返回反轉(zhuǎn)后的鏈表頭節(jié)點。輸入：單鏈表的頭節(jié)點`head`輸出：反轉(zhuǎn)后的鏈表頭節(jié)點示例：```輸入：head=[1,2,3,4,5]輸出：[5,4,3,2,1]```答案：```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverseList(head):prev=Nonecurrent=headwhilecurrent:next_node=current.nextcurrent.next=prevprev=currentcurrent=next_nodereturnprev```題目二：合并兩個有序鏈表題目描述：給定兩個有序鏈表的頭節(jié)點`l1`和`l2`，請將它們合并為一個有序鏈表，并返回合并后鏈表的頭節(jié)點。輸入：兩個有序鏈表的頭節(jié)點`l1`和`l2`輸出：合并后的有序鏈表頭節(jié)點示例：```輸入：l1=[1,2,4],l2=[1,3,4]輸出：[1,1,2,3,4,4]```答案：```pythondefmergeTwoLists(l1,l2):dummy=ListNode(0)current=dummywhilel1andl2:ifl1.val<l2.val:current.next=l1l1=l1.nextelse:current.next=l2l2=l2.nextcurrent=current.nextifl1:current.next=l1elifl2:current.next=l2returndummy.next```題目三：刪除鏈表中的重復(fù)元素題目描述：給定一個排序鏈表的頭節(jié)點`head`，請刪除所有含有重復(fù)數(shù)字的節(jié)點，只保留原始鏈表中沒有重復(fù)出現(xiàn)的數(shù)字。輸入：排序鏈表的頭節(jié)點`head`輸出：刪除重復(fù)節(jié)點后的鏈表頭節(jié)點示例：```輸入：head=[1,2,3,3,4,4,5]輸出：[1,2,5]```答案：```pythondefdeleteDuplicates(head):ifnothead:returnNonecurrent=headwhilecurrent:whilecurrent.nextandcurrent.next.val==current.val:current.next=current.next.nextcurrent=current.nextreturnhead```題目四：鏈表求和到指定值題目描述：給定一個鏈表的頭節(jié)點`head`和一個整數(shù)`sumVal`，請找出鏈表中和為`sumVal`的連續(xù)子數(shù)組，并返回這個子數(shù)組的起始節(jié)點。如果不存在這樣的子數(shù)組，則返回`None`。輸入：鏈表的頭節(jié)點`head`和整數(shù)`sumVal`輸出：子數(shù)組的起始節(jié)點示例：```輸入：head=[2,4,3],sumVal=6輸出：返回值為4的節(jié)點（值為4的第二個節(jié)點）```答案：```pythondefpairSum(head,sumVal):current=headrunning_sum=0slow=headfast=headwhilefastandfast.next:running_sum+=fast.next.valfast=fast.nextwhilerunning_sum>sumValandslow!=fast:running_sum-=slow.valslow=slow.nextifrunning_sum==sumVal:temp=slowwhiletemp.next!=fast.next:temp=temp.nextslow=slow.nextreturnslowreturnNone```題目五：鏈表的中間節(jié)點題目描述：給定一個頭節(jié)點`head`的非空單鏈表，返回鏈表的中間節(jié)點。輸入：單鏈表的頭節(jié)點`head`輸出：鏈表的中間節(jié)點示例：```輸入：head=[1,2,3,4,5]輸出：返回值為3的節(jié)點```答案：```pythondefmiddleNode(head):slow=headfast=headwhilefastandfast.next:slow=slow.ne