剑指Offer[22]-链表中倒数第k个节点

题目

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

python代码

class Solution(object):
    def getKthFromEnd(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        # step 1
        if not head:
            return None
        # step 2
        slow = head
        for i in range(k):
            head = head.next
        # step 3
        while head:
            slow = slow.next
            head = head.next
        return slow

这答题是使用快慢指针的经典例题,快指针用来指示到达链表尾部,慢指针就指向我们要寻找的位置。

  • step 1. 考虑特殊情况;
  • step 2. 快慢指针的起始位置均在头部,因为我们要找倒数第k个节点,所以我们要让快指针先移动k步;
  • step 3. 快慢指针的位置此时正好相差k个,然后同步移动,直到快指针到达尾部,此时慢指针正好在倒数第k个节点上。

发表评论

电子邮件地址不会被公开。