描述
输入一个链表，输出一个链表，该输出链表包含原链表中从倒数第k个结点至尾节点的全部节点。
如果该链表长度小于k，请返回一个长度为 0 的链表。
快慢指针
又是一个不知道的知识点。
①边界条件：如果k比链表的长度还要大，则返回None。
②设置两个指针都指向头结点，但是fast?比?slow?快k步，slow比fast慢k步，fast到尾时，距离slow为k步，即尾距离slow为k步，得到此时slow为问题的解。
！！终于完整的实现了一遍链表的操作，感谢这位博主的博客https://blog.csdn.net/kuangd_1992/article/details/104127738?utm_medium=distribute.pc_aggpage_search_result.none-task-blog-2~aggregatepage~first_rank_v2~rank_aggregation-8-104127738.pc_agg_rank_aggregation&utm_term=python%E5%A6%82%E4%BD%95%E8%BE%93%E5%85%A5%E9%93%BE%E8%A1%A8&spm=1000.2123.3001.4430
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class LinkList:
def __init__(self):
self.head = None
def initList(self, data):
# 创建头结点
self.head = ListNode(data[0])
r = self.head
p = self.head
# 逐个为 data 内的数据创建结点, 建立链表
for i in data[1:]:
node = ListNode(i)
p.next = node
p = p.next
return r
def printlist(self, head):
if head == None: return
node = head
while node != None:
print(node.val, end=' ')
node = node.next
class Solution:
def FindKthToTail(self , pHead , k ):
if k <= 0:
return None
count = 1
slow = fast = pHead
while fast != None:
if count > k:
slow = slow.next
fast = fast.next
count+=1
if count <= k:
return None
return slow.val
if __name__ == '__main__':
a = Solution()
l = LinkList()
data1 = [1, 2, 3, 4, 5]
data2 = [2, 4, 6, 8, 10]
l1 = l.initList(data1)
l2 = l.initList(data2)
l.printlist(l1)
print("\r")
l.printlist(l2)
print("\r")
m = a.FindKthToTail(l2.next, 3)
print("m=", m)
|