在单链表和双链表中删除倒数第K个节点

题目：分别实现两个函数，一个可以删除单链表中倒数第k个节点，另一个可以删除双链表中倒数第k个节点

要求：如果链表长度为N，时间复杂度达到O(N)，额外空间复杂度达到O(1)

"""单链表"""class Node:def __init__(self,value):self.value = valueself.next = Nonedef removeLastKth(head,k):if head == None or k<1:return headcur = headwhile cur!=None:k-=1cur = cur.nextif k == 0:head = head.nextelif k < 0:cur = headwhile k+1!=0:k = k+1cur = cur.nextcur.next = cur.next.nextreturn head """双链表""" class DoubleNode:def __init__(self,val):self.val = valself.next = Noneself.pre = Nonedef removeLastKth(self,k):if head == None or k < 1:return headcur = headwhile cur!=None:k -=1cur = cur.nextif k == 0:head = head.nexthead.pre = Noneelif k < 0:cur = headwhile k!=0:k +=1cur = cur.nextcur.next = cur.next.nextif cur.next!=None:cur.next.pre = curreturn head

 

总结

以上是生活随笔为你收集整理的在单链表和双链表中删除倒数第K个节点的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。