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

题目描述

输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。

例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

原题请参考链接https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

题解

方法一 【暴力破解】

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        count = 0
        cur = head
        # 计算链表长度
        while cur:
            count += 1
            cur = cur.next
        count = count - k
        # 寻找倒数第k个节点
        while count != 0:
            head = head.next
            count -= 1
        return head

方法二 【双指针】

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        # 慢指针与快指针的距离相差k-1,当快指针到达最后一个元素时,慢指针正好到达倒数第k个元素
        slow = head
        fast = head

        while k != 1 and fast.next:
            fast = fast.next
            k -= 1
        while fast.next:
            slow = slow.next
            fast = fast.next
        return slow

声明:该文章系转载,转载该文章的目的在于更广泛的传递信息,并不代表本网站赞同其观点,文章内容仅供参考。

本站是一个个人学习和交流平台,网站上部分文章为网站管理员和网友从相关媒体转载而来,并不用于任何商业目的,内容为作者个人观点, 并不代表本网站赞同其观点和对其真实性负责。

我们已经尽可能的对作者和来源进行了通告,但是可能由于能力有限或疏忽,导致作者和来源有误,亦可能您并不期望您的作品在我们的网站上发布。我们为这些问题向您致歉,如果您在我站上发现此类问题,请及时联系我们,我们将根据您的要求,立即更正或者删除有关内容。本站拥有对此声明的最终解释权。