本文共 875 字,大约阅读时间需要 2 分钟。
输入一个链表,输出该链表中倒数第k个结点。
遍历一次链表获得链表长度,再次遍历链表,至n-k+1出输出
class Solution: def FindKthToTail(self, head, k): if head == None or k < 0: return n = 1 p = head while p.next != None: p = p.next n = n + 1 if k > n: return for i in range(n-k): head = head.next return head
设置2个指针,第一个指针走K步之后,第二个指针开始从头走,这样两个指针之间始终相隔K,当指针2走到链表结尾时,指针1的位置即倒数K个节点
思路推广:寻找中间节点, 两个指针一起, 第一个指针每次走两步, 第二个指针每次走一步, 快指针指到尾部, 慢指针正好指到中间class Solution: def FindKthToTail(self, head, k): if head == None or k <= 0: return p1 = head p2 = head for i in range(k-1): if p1.next == None: return p1 = p1.next while p1.next != None: p1 = p1.next p2 = p2.next return p2
转载地址:http://qffab.baihongyu.com/