乐趣区

关于leetcode:完虐算法链表中倒数最后k个节点

链表中倒数最初 k 个节点

更多算法题解,请关注公众号【程序员学长】

问题形容

LeetCode 剑指 Offer 22. 链表中倒数第 k 个节点

输出一个链表,输入该链表中倒数第 k 个节点。为了合乎大多数人的习惯,本题从 1 开始计数,即链表的尾节点是倒数第 1 个节点。例如,一个链表有 6 个节点,从头节点开始,它们的值顺次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例:

输出:{1,2,3,4,5},2

输入:{4,5}

剖析问题

这道题比较简单,咱们能够间接应用快慢指针来求解,开始时申请两个指针同时指向链表的头结点,记为 slow 和 fast,而后让 fast 先挪动 k 步,再而后让两个指针 slow 和 fast 同时挪动,使得 fast 和 slow 在挪动的过程中总是相隔 k 个单位,当 fast 指针走到开端的时候,此时 slow 正好指向的是倒数第 k 个地位。

上面咱们来看一下代码的实现。

class Solution:
    def FindKthToTail(self, pHead, k):
        #快慢指针同时执行头结点
        slow=fast=pHead
        #快指针挪动 k 步
        for i in range(0,k):
            #如果还没走完 k 步就走到了链表尾,间接返回 None
            if not fast:‘return None
            fast = fast.next
        #两个指针同时挪动, 直到 fast 为空
        while fast:
            slow=slow.next
            fast=fast.next

        return slow
退出移动版