题目描述
输入一个链表,输出该链表中倒数第k个结点。
思路:
暴力法: 用一个list存放节点,然后取倒数第k个点。
时间复杂度 O(N)
空间复杂度 O(N)
# -*- coding:utf-8 -*-
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def FindKthToTail(self, head, k):
if not head:
return None
nodes = [head]
while head.next:
head = head.next
nodes.append(head)
if k > len(nodes) or k == 0:
return None
else:
return nodes[len(nodes)-k]
优化一下:
用快慢指针,快指针先走k步,然后慢指针再走。等到快指针为None时,慢指针为倒数第k个元素
class Solution:
def FindKthToTail(self, head, k):
if not head:
return None
quick = head
slow = head
while k > 0 and quick:
quick = quick.next
k -= 1
if k > 0:
return None
while quick:
quick = quick.next
slow = slow.next
return slow