“Successful people appear to be traveling along one continual, successful road. What is not apparent is the perseverance it takes following each defeat to keep you on that road. No one I know of has ever experienced one success after another without defeats, failures, disappointments, and frustrations galore along the way. Learning to overcome those times of agony is what separates the winners from the losers.” — G. Kingsley Ward
输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。例如,一个链表有6个节点,从头节点开始,它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
单链表是单向,所以只能顺着数,但是如果要找到倒数第 k 个节点,其实就是顺着数第 n - k + 1 个节点。
时间复杂度: O(2n)
空间复杂度:O(1)
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
cur,count = head, 0 # 这里一定要保存head的位置
while head:
count += 1
head = head.next # 第一次遍历结束后,head为空
for _ in range(count - k):
cur = cur.next # 使用cur来重新遍历
return cur
时间复杂度: O(n)
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
if head is None or k <= 0:
return None
first, second = head, head
# first一直走到k
for _ in range(k):
first = first.next
# 当first不为空,first,second一起走
while first:
first, second = first.next, second.next
# first为空,second所在的位置刚好就是倒数第k个节点
return second
递归往下走,同时增加一个count
来记录递的次数,并把结果记录在res中,当到达第k个节点时,直接返回head
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
count = 0
def helper(head):
# 边界条件
if head is None:
return None
nonlocal count
res = helper(head.next)
count += 1
if count == k:
return head
return res
return helper(head)
其实也不需要增加count,直接利用k,每一次递的过程中,对k进行减一,当k==0
,说明到达第k个节点,返回head
,不然将继续进行下去,直到head
为空。
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
def helper(head):
if head is None:
return None
nonlocal k
res = helper(head.next)
k -= 1
if k == 0:
return head
return res
return helper(head)
人生苦短,继续使用Python刷题。宇宙之一粟,下次见