首页 > 试题广场 >

链表中倒数第k个结点

[编程题]链表中倒数第k个结点
  • 热度指数:1294185 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
输入一个链表,输出该链表中倒数第k个结点。
示例1

输入

1,{1,2,3,4,5}

输出

{5}

说明:本题目包含复杂数据结构ListNode,点此查看相关信息
推荐
Python 设置两个指针,p1,p2,先让p2走k-1步,然后再一起走,直到p2为最后一个 时,p1即为倒数第k个节点
class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if head==None or k<=0:
            return None
        #设置两个指针,p2指针先走(k-1)步,然后再一起走,当p2为最后一个时,p1就为倒数第k个 数
        p2=head
        p1=head
        #p2先走,走k-1步,如果k大于链表长度则返回 空,否则的话继续走
        while k>1:
            if p2.next!=None:
                p2=p2.next
                k-=1
            else:
                return None
#两个指针一起 走,一直到p2为最后一个,p1即为所求
        while p2.next!=None:
            p1=p1.next
            p2=p2.next
        return p1


编辑于 2019-08-13 14:41:34 回复(23)